{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Create Maximum Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拼接最大数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定长度分别为&nbsp;<code>m</code>&nbsp;和&nbsp;<code>n</code>&nbsp;的两个数组，其元素由&nbsp;<code>0-9</code>&nbsp;构成，表示两个自然数各位上的数字。现在从这两个数组中选出 <code>k (k &lt;= m + n)</code>&nbsp;个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。</p>\n",
    "\n",
    "<p>求满足该条件的最大数。结果返回一个表示该最大数的长度为&nbsp;<code>k</code>&nbsp;的数组。</p>\n",
    "\n",
    "<p><strong>说明: </strong>请尽可能地优化你算法的时间和空间复杂度。</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "nums1 = <code>[3, 4, 6, 5]</code>\n",
    "nums2 = <code>[9, 1, 2, 5, 8, 3]</code>\n",
    "k = <code>5</code>\n",
    "<strong>输出:</strong>\n",
    "<code>[9, 8, 6, 5, 3]</code></pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "nums1 = <code>[6, 7]</code>\n",
    "nums2 = <code>[6, 0, 4]</code>\n",
    "k = <code>5</code>\n",
    "<strong>输出:</strong>\n",
    "<code>[6, 7, 6, 0, 4]</code></pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "nums1 = <code>[3, 9]</code>\n",
    "nums2 = <code>[8, 9]</code>\n",
    "k = <code>3</code>\n",
    "<strong>输出:</strong>\n",
    "<code>[9, 8, 9]</code></pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [create-maximum-number](https://leetcode.cn/problems/create-maximum-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [create-maximum-number](https://leetcode.cn/problems/create-maximum-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,6,5]\\n[9,1,2,5,8,3]\\n5', '[6,7]\\n[6,0,4]\\n5', '[3,9]\\n[8,9]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort()\n",
    "        res = 2 * n\n",
    "        temp = 0\n",
    "        seat = []\n",
    "        if n > len(reservedSeats):\n",
    "            n = reservedSeats[-1][0]\n",
    "        for i in range(n):\n",
    "            while reservedSeats[temp][0] - 1 == i:\n",
    "                seat.append(reservedSeats[temp][1])\n",
    "                temp += 1\n",
    "                if temp >= len(reservedSeats):\n",
    "                    break\n",
    "            if len(seat) == 1 and (seat[0] != 1 and seat[0] != 10):\n",
    "                res -= 1\n",
    "            if len(seat) >= 2:\n",
    "                if ((2 in seat or 3 in seat) and (6 in seat or 7 in seat)) or ((4 in seat or 5 in seat) and (6 in seat or 7 in seat or 8 in seat or 9 in seat)):\n",
    "                    res -= 2\n",
    "                elif 2 in seat or 3 in seat or 4 in seat or 5 in seat or 6 in seat or 7 in seat or 8 in seat or 9 in seat:\n",
    "                    res -= 1\n",
    "                else:\n",
    "                    res = res\n",
    "            seat = []\n",
    "            if temp >= len(reservedSeats):\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        res=2*n\n",
    "        l=1\n",
    "        f1=f2=f3=0\n",
    "        reservedSeats.sort()\n",
    "       # print(res)\n",
    "        for x,y in reservedSeats:\n",
    "            if x==l:\n",
    "                if 2<=y<=5:\n",
    "                    f1=1\n",
    "                if 6<=y<=9:\n",
    "                    f2=1\n",
    "                if 4<=y<=7:\n",
    "                    f3=1\n",
    "            else:\n",
    "                l=x\n",
    "                print(res,f1,f2,f3)\n",
    "                if f1==f2==f3==1:\n",
    "                    res=res-2\n",
    "                elif f1==f2==f3==0:\n",
    "                    res=res\n",
    "                else:\n",
    "                    res=res-1\n",
    "                \n",
    "                f1=0\n",
    "                f2=0\n",
    "                f3=0\n",
    "                if 2<=y<=5:\n",
    "                    f1=1\n",
    "                if 6<=y<=9:\n",
    "                    f2=1\n",
    "                if 4<=y<=7:\n",
    "                    f3=1\n",
    "                \n",
    "              #  print(res)\n",
    "        \n",
    "        if f1==f2==f3==1:\n",
    "            res=res-2\n",
    "        elif f1==f2==f3==0:\n",
    "            res=res\n",
    "        else:\n",
    "            res=res-1\n",
    "                \n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort(key=lambda x: (x[0],x[1]))\n",
    "        row = 1\n",
    "        reser = []\n",
    "        res = 0\n",
    "        last = reservedSeats[-1]\n",
    "        for i, j in reservedSeats:\n",
    "            while i > row:\n",
    "                y1 = 2 not in reser and 3 not in reser\n",
    "                y2 = 4 not in reser and 5 not in reser\n",
    "                y3 = 6 not in reser and 7 not in reser\n",
    "                y4 = 8 not in reser and 9 not in reser\n",
    "                if y1 and y2 and y3 and y4:\n",
    "                    res += 2\n",
    "                elif (y1 and y2) or (y2 and y3) or (y3 and y4):\n",
    "                    res += 1\n",
    "                row += 1\n",
    "                reser = []\n",
    "            reser.append(j)\n",
    "        y1 = 2 not in reser and 3 not in reser\n",
    "        y2 = 4 not in reser and 5 not in reser\n",
    "        y3 = 6 not in reser and 7 not in reser\n",
    "        y4 = 8 not in reser and 9 not in reser\n",
    "        if y1 and y2 and y3 and y4:\n",
    "            res += 2\n",
    "        elif (y1 and y2) or (y2 and y3) or (y3 and y4):\n",
    "            res += 1\n",
    "        res += (n-row) * 2\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats = sorted(reservedSeats)\n",
    "        res = 0\n",
    "        row = 1\n",
    "        left = True\n",
    "        middle = True\n",
    "        right = True\n",
    "        for r, c in reservedSeats:\n",
    "            # print(r,c)\n",
    "            if r > row:\n",
    "                # print(r, row, left, middle,  right)\n",
    "                row += 1\n",
    "                if left:\n",
    "                    middle = False\n",
    "                    res += 1\n",
    "                if middle:\n",
    "                    res += 1\n",
    "                    right = False\n",
    "                if right:\n",
    "                    res += 1\n",
    "                left = True\n",
    "                middle = True\n",
    "                right = True\n",
    "                if r > row:\n",
    "                    res += 2 * (r - row)\n",
    "                    row = r\n",
    "\n",
    "            if c in [2,3]:\n",
    "                left = False\n",
    "            if c in [4,5]:\n",
    "                middle = False\n",
    "                left = False\n",
    "            if c in [6,7]:\n",
    "                middle = False\n",
    "                right = False\n",
    "            if c in [8,9]:\n",
    "                right = False\n",
    "\n",
    "        # row += 1\n",
    "        # print(r, row, left, middle,  right)\n",
    "        if left:\n",
    "            middle = False\n",
    "            res += 1\n",
    "        if middle:\n",
    "            res += 1\n",
    "            right = False\n",
    "        if right:\n",
    "            res += 1\n",
    "        if n >= row:\n",
    "            res += 2 * (n - row)\n",
    "            row = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort(key=lambda x: (x[0],x[1]))\n",
    "        row = 1\n",
    "        reser = [0] * 10\n",
    "        res = 0\n",
    "        last = reservedSeats[-1]\n",
    "        for i, j in reservedSeats:\n",
    "            while i > row:\n",
    "                if reser[1:9] == [0]*8:\n",
    "                    res += 2\n",
    "                elif (reser[1:5] == [0]*4) or (reser[3:7] == [0]*4) or (reser[5:9] == [0]*4):\n",
    "                    res += 1\n",
    "                row += 1\n",
    "                reser = [0] * 10\n",
    "            reser[j-1] = 1\n",
    "        if reser[1:9] == [0]*8:\n",
    "            res += 2\n",
    "        elif (reser[1:5] == [0]*4) or (reser[3:7] == [0]*4) or (reser[5:9] == [0]*4):\n",
    "            res += 1\n",
    "        res += (n-row) * 2\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 每一行只有 2345， 4567 ， 6789三种情况可以安排\n",
    "        res = 0\n",
    "        reservedSeats = sorted(reservedSeats,key = lambda x:x[0],reverse = False)\n",
    "        seat = [1] * 10\n",
    "        line = 1\n",
    "        tmp = 0\n",
    "        for r in reservedSeats:\n",
    "            cur_line = r[0]\n",
    "            if line == cur_line:\n",
    "                seat[r[1] - 1] = 0\n",
    "                continue\n",
    "            else:\n",
    "                res += (cur_line-1-line) * 2\n",
    "                \n",
    "                if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "                    tmp += 1\n",
    "                if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "                    tmp += 1\n",
    "                if tmp == 0:\n",
    "                    if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                        tmp += 1\n",
    "                res += tmp\n",
    "\n",
    "                tmp = 0\n",
    "                seat = [1] * 10\n",
    "                line = cur_line\n",
    "                seat[r[1] - 1] = 0\n",
    "        if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "            tmp += 1\n",
    "        if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "            tmp += 1\n",
    "        if tmp == 0:\n",
    "            if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                tmp += 1\n",
    "        res += tmp\n",
    "        res += (n - line) * 2\n",
    "     \n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        idx = 0\n",
    "        num = len(reservedSeats)\n",
    "        reservedSeats.sort(key=lambda x: x[0])\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            seats = [0] * 11\n",
    "            while idx < num and reservedSeats[idx][0] == i:\n",
    "                seats[reservedSeats[idx][1]] = 1\n",
    "                idx += 1\n",
    "            if not sum(seats[2:10]):\n",
    "                res += 2\n",
    "            elif not sum(seats[2:6]) or not sum(seats[4:8]) or not sum(seats[6:10]):\n",
    "                res += 1\n",
    "            if idx == num:\n",
    "                res += (n - i) * 2\n",
    "                break\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 每一行只有 2345， 4567 ， 6789三种情况可以安排\n",
    "        res = 0\n",
    "        reservedSeats = sorted(reservedSeats,key = lambda x:x[0],reverse = False)\n",
    "        seat = [1] * 10\n",
    "        line = 1\n",
    "        tmp = 0\n",
    "        for r in reservedSeats:\n",
    "            cur_line = r[0]\n",
    "            if line == cur_line:\n",
    "                seat[r[1] - 1] = 0\n",
    "                continue\n",
    "            else:\n",
    "                res += (cur_line-1-line) * 2\n",
    "                \n",
    "                if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "                    tmp += 1\n",
    "                if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "                    tmp += 1\n",
    "                if tmp == 0:\n",
    "                    if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                        tmp += 1\n",
    "                res += tmp\n",
    "\n",
    "                tmp = 0\n",
    "                seat = [1] * 10\n",
    "                line = cur_line\n",
    "                seat[r[1] - 1] = 0\n",
    "        if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "            tmp += 1\n",
    "        if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "            tmp += 1\n",
    "        if tmp == 0:\n",
    "            if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                tmp += 1\n",
    "        res += tmp\n",
    "        res += (n - line) * 2\n",
    "     \n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        '''\n",
    "        maps={}\n",
    "        for i in range(len(reservedSeats)):\n",
    "            if reservedSeats[i][0] not in maps:\n",
    "                maps[reservedSeats[i][0]]=[1]*3\n",
    "                if reservedSeats[i][1] in [2,3,4,5]:\n",
    "                    maps[reservedSeats[i][0]][0]=0\n",
    "                if reservedSeats[i][1] in [4,5,6,7]:\n",
    "                    maps[reservedSeats[i][0]][1]=0\n",
    "                if reservedSeats[i][1] in [6,7,8,9]:\n",
    "                    maps[reservedSeats[i][0]][2]=0\n",
    "            else:\n",
    "                if reservedSeats[i][1] in [2,3,4,5]:\n",
    "                    maps[reservedSeats[i][0]][0]=0\n",
    "                if reservedSeats[i][1] in [4,5,6,7]:\n",
    "                    maps[reservedSeats[i][0]][1]=0\n",
    "                if reservedSeats[i][1] in [6,7,8,9]:\n",
    "                    maps[reservedSeats[i][0]][2]=0\n",
    "        nums=0\n",
    "        #print(maps)\n",
    "        for i in range(1,n+1):\n",
    "            if i not in maps:\n",
    "                nums+=2\n",
    "            else:\n",
    "                if maps[i][0]==1 and maps[i][2]==1:\n",
    "                    nums+=2\n",
    "                elif maps[i][0]==0 and maps[i][1]==0 and maps[i][2]==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    nums+=1\n",
    "        return nums\n",
    "        '''\n",
    "        maps={}\n",
    "        for i in range(len(reservedSeats)):\n",
    "            row=reservedSeats[i][0]\n",
    "            col=reservedSeats[i][1]\n",
    "            if col in [1,10]:\n",
    "                continue\n",
    "            if row not in maps:\n",
    "                maps[row]=[1]*3\n",
    "                if col in [2,3,4,5] and maps[row][0]==1:\n",
    "                    maps[row][0]=0\n",
    "                if col in [4,5,6,7] and maps[row][1]==1:\n",
    "                    maps[row][1]=0\n",
    "                if col in [6,7,8,9] and maps[row][2]==1:\n",
    "                    maps[row][2]=0\n",
    "            else:\n",
    "                if col in [2,3,4,5] and maps[row][0]==1:\n",
    "                    maps[row][0]=0\n",
    "                if col in [4,5,6,7] and maps[row][1]==1:\n",
    "                    maps[row][1]=0\n",
    "                if col in [6,7,8,9] and maps[row][2]==1:\n",
    "                    maps[row][2]=0\n",
    "        nums=2*(n-len(maps))\n",
    "        #print(maps)\n",
    "        for k,v in maps.items():\n",
    "            if 1 in maps[k]:\n",
    "                nums+=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        l,m,r = 0b11110000,0b11000011,0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for row,seat in reservedSeats:\n",
    "            if 2 <= seat <= 9:\n",
    "                occupied[row] |= (1 << (seat - 2))\n",
    "        \n",
    "        ret = (n - len(occupied)) * 2\n",
    "        for row,mask in occupied.items():\n",
    "            if (mask | l) == l or (mask | m) == m or (mask | r) == r:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left = 0b11110000\n",
    "        right = 0b00001111\n",
    "        mid = 0b11000011\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= 1 << (seat[1] - 2)\n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for k, v in occupied.items():\n",
    "            if (v | left) == left or (v | right) == right or (v | mid) == mid:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        check = [0b00001111, 0b11110000, 0b11000011]\n",
    "        m = defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                m[r] |= 1 << (c - 2)\n",
    "        ans = (n - len(m)) * 2\n",
    "        for val in m.values():\n",
    "            if any(x | val == x for x in check):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        left = 0b11110000\r\n",
    "        middle = 0b11000011\r\n",
    "        right = 0b00001111\r\n",
    "        x = defaultdict(int)\r\n",
    "        for i in reservedSeats:\r\n",
    "            if 2<= i[1] <=9:\r\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \r\n",
    "        ret = (n - len(x)) * 2\r\n",
    "        for value in x.values():\r\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\r\n",
    "                ret += 1\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "      M = (1 << 11) - 1\n",
    "      L = MID = R = 0\n",
    "      for i in range(2, 6):\n",
    "          L |= 1 << i\n",
    "          MID |= 1 << (i + 2)\n",
    "          R |= 1 << (i + 4)\n",
    "\n",
    "      g = dict()\n",
    "      for i, j in reservedSeats:\n",
    "          g[i] = g.get(i, M) ^ (1 << j)\n",
    "      ans = 2 * n\n",
    "      for v in g.values():\n",
    "          l = v & L == L\n",
    "          r = v & R == R\n",
    "          mid = v & MID == MID\n",
    "          if l and r:\n",
    "              continue\n",
    "          if l or r or mid:\n",
    "              ans -= 1\n",
    "          else:\n",
    "              ans -= 2\n",
    "      return ans\n",
    "              \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, right, mid = 0b00001111, 0b11110000, 0b11000011\n",
    "        m = defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                m[r] |= 1 << (c - 2)\n",
    "        ans = (n - len(m)) * 2\n",
    "        for val in m.values():\n",
    "            if val | left == left or val | right == right or val | mid == mid:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        res = n * 2\n",
    "        reserved_dict = {}\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                if x not in reserved_dict:\n",
    "                    reserved_dict[x] = []\n",
    "                reserved_dict[x].append(y)\n",
    "        \n",
    "        for x in reserved_dict:\n",
    "            res -= 2\n",
    "            reserved_list = sorted(reserved_dict[x])\n",
    "            if len(reserved_list) > 4:\n",
    "                continue\n",
    "            \n",
    "            if len(reserved_list) == 1:\n",
    "                res += 1\n",
    "            elif reserved_list[0] > 5:\n",
    "                res += 1\n",
    "            elif reserved_list[-1] < 6:\n",
    "                res += 1\n",
    "            elif reserved_list[0] < 4 and reserved_list[-1] > 7:\n",
    "                if len(reserved_list) == 2:\n",
    "                    res += 1\n",
    "                elif len(reserved_list) == 3 and (reserved_list[1] < 4 or reserved_list[1] > 7):\n",
    "                    res += 1\n",
    "                elif reserved_list[1] == 3 and reserved_list[2] == 8:\n",
    "                    res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        families = n * 2\n",
    "\n",
    "        seats = defaultdict(list)\n",
    "\n",
    "        for r, c in reservedSeats:\n",
    "            seats[r].append(c)\n",
    "\n",
    "        for r, cs in seats.items():\n",
    "            left = True\n",
    "            right = True\n",
    "            mid = True\n",
    "            for c in cs:\n",
    "                if c in [2, 3, 4, 5]:\n",
    "                    left = False\n",
    "                if c in [6, 7, 8, 9]:\n",
    "                    right = False\n",
    "                if c in [4, 5, 6, 7]:\n",
    "                    mid = False\n",
    "\n",
    "            if not left:\n",
    "                families -= 1\n",
    "            if not right:\n",
    "                families -= 1\n",
    "            if not left and not right and mid:\n",
    "                families += 1\n",
    "\n",
    "        return families"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        ans -= len(d)\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        mode_left = 0b00001111\n",
    "        mode_mid = 0b11000011\n",
    "        mode_right = 0b11110000\n",
    "\n",
    "        row_state = collections.defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                row_state[r] |= (1 << (c - 2))\n",
    "                \n",
    "        res = (n - len(row_state)) * 2\n",
    "        for r, state in row_state.items():\n",
    "            if (state | mode_left) == mode_left or (state | mode_mid) == mode_mid or (state | mode_right) == mode_right:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left = 0b11110000\n",
    "        middle = 0b11000011\n",
    "        right = 0b00001111\n",
    "        x = defaultdict(int)\n",
    "        for i in reservedSeats:\n",
    "            if 2<= i[1] <=9:\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \n",
    "        ret = (n - len(x)) * 2\n",
    "        for value in x.values():\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\n",
    "                ret += 1\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        a = {i[0]:7 for i in reservedSeats} #分别设定了3个二进制位分别代表坐下的三种情况。\n",
    "        la = len(a)\n",
    "        # print(a)\n",
    "        cnt = (n - la)*2 #这些行没人坐 每排两个\n",
    "        # print(cnt)\n",
    "        for i in reservedSeats: #对有人坐的行进行标记\n",
    "            if  2 <= i[1] <= 3:\n",
    "                a[i[0]] = a[i[0]] & 6\n",
    "            elif 8 <= i[1] <= 9:\n",
    "                a[i[0]] = a[i[0]] & 5\n",
    "            elif 4 <= i[1] <= 5:\n",
    "                a[i[0]] = a[i[0]] & 2\n",
    "            elif 6 <= i[1] <= 7:\n",
    "                a[i[0]] = a[i[0]] & 1\n",
    "            \n",
    "            # print(i, a[i[0]])\n",
    "        for i in a.items(): #对有人做的计数\n",
    "            if i[1] == 7:\n",
    "                cnt += 2\n",
    "            elif i[1] == 0:\n",
    "                cnt += 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 2)\n",
    "        ret = (n - len(cnt)) * 2\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        for v in cnt.values():\n",
    "            if left | v == left or middle | v == middle or right | v == right:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right)== right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        a = {i[0]:7 for i in reservedSeats} #分别设定了3个二进制位分别代表坐下的三种情况。\n",
    "        la = len(a)\n",
    "        # print(a)\n",
    "        cnt = (n - la)*2 #这些行没人坐 每排两个\n",
    "        # print(cnt)\n",
    "        for i in reservedSeats: #对有人坐的行进行标记\n",
    "            if  2 <= i[1] <= 3:\n",
    "                a[i[0]] = a[i[0]] & 6\n",
    "            elif 8 <= i[1] <= 9:\n",
    "                a[i[0]] = a[i[0]] & 5\n",
    "            elif 4 <= i[1] <= 5:\n",
    "                a[i[0]] = a[i[0]] & 2\n",
    "            elif 6 <= i[1] <= 7:\n",
    "                a[i[0]] = a[i[0]] & 1\n",
    "            \n",
    "            # print(i, a[i[0]])\n",
    "        for i in a.items(): #对有人做的计数\n",
    "            if i[1] == 7:\n",
    "                cnt += 2\n",
    "            elif i[1] == 0:\n",
    "                cnt += 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 2, 3, 4, 5, 0b11110\n",
    "        # 4, 5, 6, 7, 0b1111000\n",
    "        # 6, 7, 8, 9, 0b111100000\n",
    "        # reserved 2, 3, 8, 0b10000110\n",
    "        left, middle, right = 0b11110, 0b1111000, 0b111100000\n",
    "        l = len(reservedSeats)\n",
    "        i = 1\n",
    "        j = 0\n",
    "        row_reserved = {}\n",
    "        for r, c in reservedSeats:\n",
    "            # process each reserved seat into dict showing reserved status (int) for the row\n",
    "            row_reserved[r] = row_reserved.get(r, 0) + (1 << (c - 1))\n",
    "        res = 2 * (n - len(row_reserved))   # start with non reserved rows\n",
    "\n",
    "        for row, reserved in row_reserved.items():\n",
    "            if left & reserved == 0 and right & reserved == 0:\n",
    "                res += 2\n",
    "            elif middle & reserved == 0 or left & reserved == 0 or right & reserved == 0:\n",
    "                res += 1\n",
    "\n",
    "        # reservedSeats.sort()  # sort not necessary after using dict, TC: O(nlog(n)) to O(n)\n",
    "        # while i <= n:\n",
    "            # reserved = 0\n",
    "            # while j < l and reservedSeats[j][0] == i:\n",
    "            #     reserved += 1 << (reservedSeats[j][1] - 1)\n",
    "            #     j += 1\n",
    "\n",
    "            # if reserved == 0 or (left & reserved == 0 and right & reserved == 0):\n",
    "            #     res += 2\n",
    "            # elif middle & reserved == 0 or left & reserved == 0 or right & reserved == 0:\n",
    "            #     res += 1\n",
    "\n",
    "            # # i += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        ret = 0\n",
    "        for v in cnt.values():\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret + (n - len(cnt)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        bit_mapping = defaultdict(int)\n",
    "        left = 0b00001111\n",
    "        right = 0b11110000\n",
    "        mid = 0b11000011\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1]  <= 9:\n",
    "                bit_mapping[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        result = (n - len(bit_mapping)) * 2\n",
    "        for row, bit in bit_mapping.items():\n",
    "            if (bit | left) == left or (bit | right) == right or (bit | mid) == mid:\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "\n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 2\n",
    "            elif l or m or r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxNumberOfFamilies(self, n, res):\n",
    "        left = set()\n",
    "        right = set()\n",
    "        mid = set()\n",
    "        count = 0\n",
    "        min_, max_ = n, 0\n",
    "        for r, c in res:\n",
    "            min_ = min(r, min_)\n",
    "            max_ = max(r, max_)\n",
    "            if r in left and r in right and r in mid:\n",
    "                continue\n",
    "            if (c < 6) and (c > 1): left.add(r)\n",
    "            if (c < 10) and (c > 5): right.add(r)\n",
    "            if (c < 8) and (c > 3): mid.add(r)\n",
    "        for i in range(min_, max_+1):\n",
    "            if i not in left and i not in right:\n",
    "                count += 2\n",
    "            elif i not in mid:\n",
    "                count += 1\n",
    "            elif i not in left or i not in right:\n",
    "                count += 1\n",
    "        count += 2*(min_-1)\n",
    "        count += 2*(n-max_)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for x, y in reservedSeats:\n",
    "            insort_left(d[x], y)\n",
    "        ans = (n - len(d)) * 2\n",
    "        for l in d.values():\n",
    "            l.insert(0, 0)\n",
    "            l.append(11)\n",
    "            for i in range(1, len(l)):\n",
    "                if l[i - 1] < 2 and l[i] > 9:\n",
    "                    ans += 2\n",
    "                elif l[i - 1] < 2 and l[i] > 5 or l[i - 1] < 4 and l[i] > 7 or l[i - 1] < 6 and l[i] > 9:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 使用8个二进制位来表示一排座位的预约情况。\n",
    "        # 9 8 7 6 5 4 3 2\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "\n",
    "        for seat in reservedSeats:\n",
    "            if 2<=seat[1]<=9:\n",
    "                occupied[seat[0]] = occupied[seat[0]] | (1<<(seat[1]-2))\n",
    "\n",
    "        res = (n-len(occupied)) * 2\n",
    "        for row,bitmask in occupied.items():\n",
    "            if (bitmask | left)==left or (bitmask | middle)==middle or (bitmask | right)==right:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "cnt = [2, 1, 1, 1, 1, 0, 0, 0, 1, 1,0,0,1,0,0,0]\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        rsv = defaultdict(int)\n",
    "        for row, col in reservedSeats:\n",
    "            if 2<=col<=3 and not (rsv[row-1] >> 3) & 1:\n",
    "                rsv[row-1] += 8\n",
    "            elif 4<=col<=5 and not (rsv[row-1] >> 2) & 1:\n",
    "                rsv[row-1] += 4\n",
    "            elif 6<=col<=7 and not (rsv[row-1] >> 1) & 1:\n",
    "                rsv[row-1] += 2\n",
    "            elif 8<=col<=9 and not (rsv[row-1] & 1):\n",
    "                rsv[row-1] += 1\n",
    "        ans = n*2\n",
    "        for r in rsv.values():\n",
    "            ans += cnt[r]-2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 首先按行，将reservedSeats分组。\n",
    "        # 2345,4567，6789 \n",
    "        rec = defaultdict(list)\n",
    "        for r,c in reservedSeats:\n",
    "            rec[r].append(c)\n",
    "        total = 0\n",
    "        for r,clist in rec.items():\n",
    "            f1,f2,f3 = True, True, True\n",
    "            for c in clist:\n",
    "                if c in [2,3,4,5]: f1 = False\n",
    "                if c in [4,5,6,7]: f2 = False\n",
    "                if c in [6,7,8,9]: f3 = False\n",
    "            if f1 and f3:\n",
    "                total += 2\n",
    "            elif f1 or f2 or f3:\n",
    "                total += 1\n",
    "            pass\n",
    "        total += 2*(n - len(rec))\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "        tplan = 0   \n",
    "        rowrsi = {}\n",
    "        for seat in reservedSeats:\n",
    "            if seat[0] not in rowrsi:\n",
    "                rowrsi[seat[0]] = [] \n",
    "                rowrsi[seat[0]].append(seat[1])\n",
    "            else:\n",
    "                rowrsi[seat[0]].append(seat[1])\n",
    "        for rowrsii in rowrsi:\n",
    "            tplan += self.rowplan(rowrsi[rowrsii]) \n",
    "        return tplan + (n - len(rowrsi))*2\n",
    "\n",
    "    def rowplan(self, rowrs):\n",
    "        if sum([i not in rowrs for i in range(2,10)]) ==8:\n",
    "            return 2\n",
    "        if sum([i not in rowrs for i in range(4,8)]) == 4:\n",
    "            return 1\n",
    "        if sum([i not in rowrs for i in range(2,6)]) ==4 or sum([i not in rowrs for i in range(6,10)])==4:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        mode_left = 0b00001111\n",
    "        mode_mid = 0b11000011\n",
    "        mode_right = 0b11110000\n",
    "\n",
    "        row_state = collections.defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                row_state[r] |= (1 << (c - 2))\n",
    "                \n",
    "        res = (n - len(row_state)) * 2\n",
    "        for r, state in row_state.items():\n",
    "            if (state | mode_left) == mode_left or (state | mode_mid) == mode_mid or (state | mode_right) == mode_right:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedList = defaultdict(list)\n",
    "        for c, r in reservedSeats:\n",
    "            reservedList[c].append(r - 1)\n",
    "        mask1, mask2, mask3, mask4 = 0b0111111110, 0b111100000, 0b1111000, 0b11110\n",
    "        ret = 0\n",
    "        for j in reservedList.keys():\n",
    "            current = 0\n",
    "            for i in range(10):\n",
    "                current = (current << 1) + (i in reservedList[j])\n",
    "            ret += (current & mask1 == 0) + ((current & mask2 == 0) | (current & mask3 == 0) | (current & mask4 == 0))\n",
    "            # print(ret, acc)\n",
    "        return ret + (n - len(reservedList)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        seat = defaultdict(int)\n",
    "        for a, b in reservedSeats:\n",
    "            seat[a] |= 1 << b\n",
    "\n",
    "        ans = (n - len(seat)) * 2\n",
    "        two = sum(1 << x for x in range(2, 10))\n",
    "        left = sum(1 << x for x in range(2, 6))\n",
    "        mid = sum(1 << x for x in range(4, 8))\n",
    "        right = sum(1 << x for x in range(6, 10))\n",
    "\n",
    "        for i in seat:\n",
    "            if not two & seat[i]:\n",
    "                ans += 2\n",
    "            else:\n",
    "                for one in [left, mid, right]:\n",
    "                    if not one & seat[i]:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "L = 0b0111100000\n",
    "M = 0b0001111000\n",
    "R = 0b0000011110\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        ans -= len(d)\n",
    "        for v in d.values():\n",
    "            if L & v and M & v and R & v:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ans = n * 2\n",
    "        d = defaultdict(list)\n",
    "        for (i,j) in reservedSeats:\n",
    "            d[i].append(j)\n",
    "        for i in d:\n",
    "            arr = d[i]\n",
    "            left,right,mid = 0,0,1\n",
    "            for j in arr:\n",
    "                if 1< j < 6:\n",
    "                    left = -1\n",
    "                if 3< j < 8:\n",
    "                    mid = 0\n",
    "                if 5 < j < 10:\n",
    "                    right = -1\n",
    "            if left and right:\n",
    "                ans -= 2 - mid\n",
    "            else:\n",
    "                ans += left + right\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        que = defaultdict(list)\n",
    "        for a, b in reservedSeats:\n",
    "            que[a].append(b)\n",
    "        base = (n - len(que)) * 2\n",
    "        for k, v in que.items():\n",
    "            tmp = [0] * 11\n",
    "            for vv in v:\n",
    "                tmp[vv] = 1\n",
    "            acc = list(accumulate(tmp, initial=0))\n",
    "            if acc[10] - acc[2] == 0:\n",
    "                base += 2\n",
    "            elif acc[6] - acc[2] == 0:\n",
    "                base += 1\n",
    "            elif acc[10] - acc[6] == 0:\n",
    "                base += 1\n",
    "            elif acc[8] - acc[4] == 0:\n",
    "                base += 1\n",
    "        return base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        left = 0b11110000\r\n",
    "        middle = 0b11000011\r\n",
    "        right = 0b00001111\r\n",
    "        x = defaultdict(int)\r\n",
    "        for i in reservedSeats:\r\n",
    "            if 2<= i[1] <=9:\r\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \r\n",
    "        ret = (n - len(x)) * 2\r\n",
    "        for value in x.values():\r\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\r\n",
    "                ret += 1\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        ret = (n - len(cnt)) * 2\n",
    "        for v in cnt.values():\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "_FAM_1 = int(\"11110\", 2)\n",
    "_FAM_2 = int(\"1111000\", 2)\n",
    "_FAM_3 = int(\"111100000\", 2)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reserved_seats: List[List[int]]) -> int:\n",
    "        def check_fam_num(row: int) -> int:\n",
    "\n",
    "            l = row & _FAM_1 == 0\n",
    "            r = row & _FAM_3 == 0\n",
    "\n",
    "            if l or r:\n",
    "                return int(l) + int(r)\n",
    "            \n",
    "            return int(row & _FAM_2 == 0)\n",
    "        res = defaultdict(int)\n",
    "        for r, c in reserved_seats:\n",
    "            res[r] |= 1 << c - 1\n",
    "        return (n - len(res)) * 2 + sum(check_fam_num(row) for _, row in res.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedList = defaultdict(list)\n",
    "        for c, r in reservedSeats:\n",
    "            reservedList[c].append(r)\n",
    "        ret = 0\n",
    "        for j in reservedList.keys():\n",
    "            current = [0] * 10\n",
    "            for i in reservedList[j]:\n",
    "                current[i - 1] = 1\n",
    "            acc = list(accumulate(current))\n",
    "            ret += (acc[8] - acc[0] == 0) + ((acc[4] - acc[0] == 0) | (acc[6] - acc[2] == 0) | (acc[8] - acc[4] == 0))\n",
    "            # print(ret, acc)\n",
    "        return ret + (n - len(reservedList)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            d[i] += 1 << j - 1\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 2\n",
    "            elif l or m or r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 首先按行，将reservedSeats分组。\n",
    "        # 2345,4567，6789\n",
    "        # 遍历reverse，根据三个区间是否被占，计算reverse中能放下的家庭数\n",
    "        # 其余没有被占的行，每行都可以放2个家庭\n",
    "        rec = defaultdict(list)\n",
    "        for r,c in reservedSeats:\n",
    "            rec[r].append(c)\n",
    "        total = 0\n",
    "        for r,clist in rec.items():\n",
    "            f1,f2,f3 = True, True, True\n",
    "            for c in clist:\n",
    "                if c in [2,3,4,5]: f1 = False\n",
    "                if c in [4,5,6,7]: f2 = False\n",
    "                if c in [6,7,8,9]: f3 = False\n",
    "            if f1 and f3:\n",
    "                total += 2\n",
    "            elif f1 or f2 or f3:\n",
    "                total += 1\n",
    "            pass\n",
    "        total += 2*(n - len(rec))\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        occ = defaultdict(list)\n",
    "        for line, seat in reservedSeats:\n",
    "            occ[line].append(seat)\n",
    "        ans = 0\n",
    "        for line in occ:\n",
    "            n -= 1\n",
    "            seats_occupied = [False] * 11\n",
    "            for seat in occ[line]:\n",
    "                seats_occupied[seat] = True\n",
    "            if sum(seats_occupied[2: 10]) == 0:\n",
    "                ans += 2\n",
    "            elif sum(seats_occupied[2: 6]) == 0:\n",
    "                ans += 1\n",
    "            elif sum(seats_occupied[6: 10]) == 0:\n",
    "                ans += 1\n",
    "            elif sum(seats_occupied[4: 8]) == 0:\n",
    "                ans += 1\n",
    "        ans += (n * 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        seats = {}\n",
    "        result = 0\n",
    "        for a, b in reservedSeats:\n",
    "            if a-1 not in seats:\n",
    "                seats[a-1] = [0] *10\n",
    "            seats[a-1][b-1] = 1\n",
    "        for row in seats.values():\n",
    "            if not any(row[1:9]):\n",
    "                result += 2\n",
    "            elif not any(row[1:5]) or not any(row[5:9]) or not any(row[3:7]):\n",
    "                result += 1\n",
    "        result += 2*(n-len(seats))\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        rowrsi = defaultdict(list)\n",
    "        for seat in reservedSeats:\n",
    "            rowrsi[seat[0]].append(seat[1])\n",
    "        \n",
    "        tplan = 0\n",
    "        for row in rowrsi.values():\n",
    "            tplan += self.rowplan(row)\n",
    "        \n",
    "        empty_rows = n - len(rowrsi)\n",
    "        return tplan + empty_rows * 2\n",
    "    \n",
    "    def rowplan(self, rowrs):\n",
    "        occupied = set(rowrs)\n",
    "        \n",
    "        if all(i not in occupied for i in range(2, 10)):\n",
    "            return 2\n",
    "        if all(i not in occupied for i in range(4, 8)):\n",
    "            return 1\n",
    "        if all(i not in occupied for i in range(2, 6)) or all(i not in occupied for i in range(6, 10)):\n",
    "            return 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        print(cnt)\n",
    "        ret = 0\n",
    "        for v in cnt.values():\n",
    "            print(bin(v))\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret + (n - len(cnt)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        res=n*2\n",
    "        dit = collections.defaultdict(lambda:[0 for i in range(11)])\n",
    "        for i in reservedSeats:\n",
    "            dit[i[0]][i[1]]=1\n",
    "        for i in dit:\n",
    "            chair=dit[i]\n",
    "            if chair[2:6]!=[0,0,0,0] or chair[6:10]!=[0,0,0,0]:\n",
    "                res-= 2\n",
    "                if chair[2:6]==[0,0,0,0] or chair[6:10]==[0,0,0,0] or chair[4:8]==[0,0,0,0]:\n",
    "                    res+=1  \n",
    "     \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        row2cols = defaultdict(set)\n",
    "        for row, col in reservedSeats:\n",
    "            if col != 1 and col != 10:\n",
    "                row2cols[row].add(col)\n",
    "\n",
    "        res = (n - len(row2cols)) * 2\n",
    "\n",
    "        for cols in row2cols.values():\n",
    "            # {2, 3, 4, 5} {4, 5, 6, 7}, {6, 7, 8, 9}\n",
    "            \n",
    "            if (all(col not in cols for col in {2, 3, 4, 5}) or \n",
    "                all(col not in cols for col in {4, 5, 6, 7}) or \n",
    "                all(col not in cols for col in {6, 7, 8, 9})):\n",
    "                res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        rsv = defaultdict(set)\r\n",
    "\r\n",
    "        for x, y in reservedSeats:\r\n",
    "            if 1 < y < 10:\r\n",
    "                rsv[x].add(y)\r\n",
    "\r\n",
    "        ret = (n - len(rsv)) * 2\r\n",
    "\r\n",
    "        for i in rsv:\r\n",
    "            if 2 not in rsv[i] and 3 not in rsv[i] and 4 not in rsv[i] and 5 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            elif 4 not in rsv[i] and 5 not in rsv[i] and 6 not in rsv[i] and 7 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            elif 6 not in rsv[i] and 7 not in rsv[i] and 8 not in rsv[i] and 9 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            # print(i, ret)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        row2cols = defaultdict(set)\n",
    "        for row, col in reservedSeats:\n",
    "            row2cols[row].add(col)\n",
    "\n",
    "        res = (n - len(row2cols)) * 2\n",
    "\n",
    "        for cols in row2cols.values():\n",
    "            # {2, 3, 4, 5} {4, 5, 6, 7}, {6, 7, 8, 9}\n",
    "            \n",
    "            if all(col not in cols for col in {2, 3, 4, 5, 6, 7, 8, 9}):\n",
    "                res += 2\n",
    "            elif (all(col not in cols for col in {2, 3, 4, 5}) or \n",
    "                  all(col not in cols for col in {4, 5, 6, 7}) or \n",
    "                  all(col not in cols for col in {6, 7, 8, 9})):\n",
    "                  res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def get_max(nums,l):\n",
    "            l=min(l,len(nums))\n",
    "            st=[]\n",
    "            for num in nums:\n",
    "                if not st:\n",
    "                    st.append(num)\n",
    "                else:\n",
    "                    while st and num > st[-1] and l>0:\n",
    "                        st.pop()\n",
    "                        l-=1\n",
    "                    st.append(num)\n",
    "            return st[:-l] if l>0 else st\n",
    "        def merge(a1,a2):\n",
    "            a=[]\n",
    "            while a1 or a2:\n",
    "                a.append(a2.pop(0) if a1<a2 else a1.pop(0))\n",
    "            return a\n",
    "        ans=[]\n",
    "        for m in range(k+1):\n",
    "            n=k-m\n",
    "            if m<=len(nums1) and n<=len(nums2):\n",
    "                arr1=get_max(nums1,len(nums1)-m)\n",
    "                arr2=get_max(nums2,len(nums2)-n)\n",
    "                ans=max(ans,merge(arr1,arr2))\n",
    "                #print(m,n,arr1,arr2,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        res = [-inf] * k\n",
    "\n",
    "        # 将两个stk进行合并，利用列表比较大小的性质\n",
    "        def merge(stk1, stk2):\n",
    "            res = []\n",
    "            while stk1 or stk2:\n",
    "                mx = max(stk1, stk2)\n",
    "                res.append(mx.popleft())\n",
    "            return res\n",
    "\n",
    "        def pick(nums, q):\n",
    "            stk, n = deque(), len(nums)\n",
    "            for i, x in enumerate(nums):\n",
    "                # 判断是否能够拼接\n",
    "                while stk and x > stk[-1] and len(stk) - 1 + (n - i) >= q:\n",
    "                    stk.pop()\n",
    "                if len(stk) < q:\n",
    "                    stk.append(x)\n",
    "            return stk\n",
    "\n",
    "        # 确定枚举范围\n",
    "        l = max(0, k - len(nums2))\n",
    "        r = min(k, len(nums1)) \n",
    "        # 枚举nums1中选数的个数（对应nums2的也就确定）\n",
    "        for q in range(l, r + 1):\n",
    "            res = max(res, merge(pick(nums1, q), pick(nums2, k - q)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        maxSubsequence = [0] * k\n",
    "        start, end = max(0, k - n), min(k, m)\n",
    "\n",
    "        for i in range(start, end + 1):\n",
    "            subsequence1 = self.getMaxSubsequence(nums1, i)\n",
    "            subsequence2 = self.getMaxSubsequence(nums2, k - i)\n",
    "            curMaxSubsequence = self.merge(subsequence1, subsequence2)\n",
    "            if self.compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0:\n",
    "                maxSubsequence = curMaxSubsequence\n",
    "        \n",
    "        return maxSubsequence\n",
    "\n",
    "    def getMaxSubsequence(self, nums: List[int], k: int) -> int:\n",
    "        stack = [0] * k\n",
    "        top = -1\n",
    "        remain = len(nums) - k\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            while top >= 0 and stack[top] < num and remain > 0:\n",
    "                top -= 1\n",
    "                remain -= 1\n",
    "            if top < k - 1:\n",
    "                top += 1\n",
    "                stack[top] = num\n",
    "            else:\n",
    "                remain -= 1\n",
    "        \n",
    "        return stack\n",
    "\n",
    "    def merge(self, subsequence1: List[int], subsequence2: List[int]) -> List[int]:\n",
    "        x, y = len(subsequence1), len(subsequence2)\n",
    "        if x == 0:\n",
    "            return subsequence2\n",
    "        if y == 0:\n",
    "            return subsequence1\n",
    "        \n",
    "        mergeLength = x + y\n",
    "        merged = list()\n",
    "        index1 = index2 = 0\n",
    "\n",
    "        for _ in range(mergeLength):\n",
    "            if self.compare(subsequence1, index1, subsequence2, index2) > 0:\n",
    "                merged.append(subsequence1[index1])\n",
    "                index1 += 1\n",
    "            else:\n",
    "                merged.append(subsequence2[index2])\n",
    "                index2 += 1\n",
    "        \n",
    "        return merged\n",
    "\n",
    "    def compare(self, subsequence1: List[int], index1: int, subsequence2: List[int], index2: int) -> int:\n",
    "        x, y = len(subsequence1), len(subsequence2)\n",
    "        while index1 < x and index2 < y:\n",
    "            difference = subsequence1[index1] - subsequence2[index2]\n",
    "            if difference != 0:\n",
    "                return difference\n",
    "            index1 += 1\n",
    "            index2 += 1\n",
    "        \n",
    "        return (x - index1) - (y - index2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def selectMax(nums,k):\n",
    "            stack = []\n",
    "            remain = len(nums) - k\n",
    "            for num in nums:\n",
    "                while remain and stack and num > stack[-1]:\n",
    "                    stack.pop()\n",
    "                    remain -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "        \n",
    "        def merge(A,B):\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = max(A,B)\n",
    "                ans.append(bigger[0])\n",
    "                bigger.pop(0)\n",
    "            return ans\n",
    "        maxlist = [0] * k\n",
    "        for i in range(k + 1):\n",
    "            if i <= len(nums1) and k - i <= len(nums2):\n",
    "                maxlist = max(maxlist,merge(selectMax(nums1,i),selectMax(nums2,k - i)))\n",
    "        return maxlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        res = [-inf] * k\n",
    "        def merge(stk1, stk2):\n",
    "            res = []\n",
    "            while stk1 or stk2:\n",
    "                mx = max(stk1, stk2)\n",
    "                res.append(mx.popleft())\n",
    "            return res\n",
    "        def pick(nums, q):\n",
    "            stk, n = deque(), len(nums)\n",
    "            for i, x in enumerate(nums):\n",
    "                while stk and x > stk[-1] and len(stk) - 1 + (n - i) >= q:\n",
    "                    stk.pop()\n",
    "                if len(stk) < q:\n",
    "                    stk.append(x)\n",
    "            return stk\n",
    "        l = 0 if len(nums2) >= k else k - len(nums2)\n",
    "        r = min(k, len(nums1)) \n",
    "        for q in range(l, r + 1):\n",
    "            res = max(res, merge(pick(nums1, q), pick(nums2, k - q)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        def remake(ls):\n",
    "            ret=[]\n",
    "            n=len(ls)\n",
    "            ret.append(2**n-1)\n",
    "            for j in range(1,n):\n",
    "                for i in range(j-1,-1,-1):\n",
    "                    if not ret[-1]>>n-i-1 &1:\n",
    "                        continue\n",
    "                    if ls[i]<ls[j]:\n",
    "                        ret.append(ret[-1]^(1<<n-i-1))\n",
    "            for j in range(n):\n",
    "                if ret[-1]&(1<<j):\n",
    "                    ret.append(ret[-1]^(1<<j))\n",
    "            ret.reverse()\n",
    "            return ret\n",
    "        ls1=remake(nums1)\n",
    "        ls2=remake(nums2)\n",
    "        def cal(x1,x2):\n",
    "            l1,l2=[],[]\n",
    "            for i in range(m):\n",
    "                if x1>>i &1:\n",
    "                    l1.append(nums1[-i-1])\n",
    "            for j in range(n):\n",
    "                if x2>>j &1:\n",
    "                    l2.append(nums2[-j-1])\n",
    "            l1.reverse()\n",
    "            l2.reverse()\n",
    "            l,r=0,0\n",
    "            ll,rr=len(l1),len(l2)\n",
    "            ret=[]\n",
    "            while l<ll and r<rr:\n",
    "                if l1[l]>l2[r]:\n",
    "                    ret.append(l1[l])\n",
    "                    l+=1\n",
    "                elif l1[l]==l2[r] and  l1[l+1:]>l2[r+1:]:\n",
    "                    ret.append(l1[l])\n",
    "                    l+=1\n",
    "                else:\n",
    "                    ret.append(l2[r])\n",
    "                    r+=1\n",
    "            ret+=l1[l:]+l2[r:]\n",
    "            return ret\n",
    "        ret=(nums1+nums2)[:k]\n",
    "        for i in range(m+1):\n",
    "            if i>k:\n",
    "                break\n",
    "            j=k-i\n",
    "            if j>n:\n",
    "                continue\n",
    "            now=cal(ls1[i],ls2[j])\n",
    "            if now >ret:\n",
    "                ret=now\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "\n",
    "        def pick_max(nums, k): ### 在保持相对顺序的情况下删掉drop个数字，让值最大 单调递减栈\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while drop and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "\n",
    "        def merge(A, B): ### 生成组合后的列表\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                #print(A)\n",
    "                bigger = A if A > B else B ### 这是在比较栈的第一个值吗,两个列表比大小\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "        return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))\n",
    "\n",
    "# 作者：lucifer\n",
    "# 链接：https://leetcode.cn/problems/create-maximum-number/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "getMax() 的时间复杂度为 O(M + N), 其中 M, N 表示 数组 nums1, nums2 的长度.\n",
    "merge() 的时间复杂度为 O(k), k 为 条件中的 k .\n",
    "再加上外层遍历所有的 k 中可能性.\n",
    "因此时间复杂度为 O(k(k + N + M))\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        # 将两个的结果合并\n",
    "        def merge(A, B):\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "        \n",
    "        # 数组nums, 能得到 最大的长度为k的数组\n",
    "        def getMax(nums: List[int], k: int) -> List[int]:\n",
    "            st = []\n",
    "            del_k = len(nums) - k   # 要删除的个数\n",
    "            for x in nums:\n",
    "                while st and del_k and x > st[-1]:\n",
    "                    st.pop()\n",
    "                    del_k -= 1\n",
    "                st.append(x)\n",
    "            \n",
    "            return st[:k]\n",
    "\n",
    "        return max(merge(getMax(nums1, i), getMax(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def pick_max(nums: List[int], k):\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while stack and num > stack[-1] and drop:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "        def merge(A, B):\n",
    "            AA = A[:]\n",
    "            BA = B[:]\n",
    "            ans = []\n",
    "            while AA and BA:\n",
    "                if AA > BA:\n",
    "                    ans.append(AA[0])\n",
    "                    AA.pop(0)\n",
    "                else:\n",
    "                    ans.append(BA[0])\n",
    "                    BA.pop(0)\n",
    "            if AA:\n",
    "                ans.extend(AA)\n",
    "            else:\n",
    "                ans.extend(BA)\n",
    "            return ans\n",
    "        \n",
    "        return max(merge(pick_max(nums1, i), pick_max(nums2, k - i)) for i in range(k+ 1) if i <= len(nums1) and k - i <= len(nums2))\n",
    "\n",
    "# class Solution:\n",
    "#     def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "#         def pick_max(nums, k):\n",
    "#             stack = []\n",
    "#             drop = len(nums) - k\n",
    "#             for num in nums:\n",
    "#                 while drop and stack and num > stack[-1]:\n",
    "#                     stack.pop()\n",
    "#                     drop -= 1\n",
    "#                 stack.append(num)\n",
    "#             return stack[:k]\n",
    "#         def merge(A, B):\n",
    "#             ans = []\n",
    "#             while A or B:\n",
    "#                 bigger = A if A > B else B\n",
    "#                 ans.append(bigger[0])\n",
    "#                 bigger.pop(0)\n",
    "#             return ans\n",
    "        \n",
    "#         return max(merge(pick_max(nums1, i), pick_max(nums2, k - i)) for i in range(k+ 1) if i <= len(nums1) and k - i <= len(nums2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\r\n",
    "        m, n = len(nums1), len(nums2)\r\n",
    "        start, end = max(0, k - n), min(m, k)\r\n",
    "        ans = []\r\n",
    "        for i in range(start, end + 1):\r\n",
    "            l = self.merge(self.fetch(nums1, i), self.fetch(nums2, k - i))\r\n",
    "            if l > ans:\r\n",
    "                ans = l\r\n",
    "        return ans\r\n",
    "\r\n",
    "    def fetch(self, nums, cnt):\r\n",
    "        n, stack = len(nums), []\r\n",
    "        remove_cnt = n - cnt\r\n",
    "        for i in range(n):\r\n",
    "            while stack and stack[-1] < nums[i] and remove_cnt > 0:\r\n",
    "                stack.pop()\r\n",
    "                remove_cnt -= 1\r\n",
    "            stack.append(nums[i])\r\n",
    "        return stack[:cnt]\r\n",
    "    \r\n",
    "    def merge(self, l1, l2):\r\n",
    "        if not l1:\r\n",
    "            return l2\r\n",
    "        if not l2:\r\n",
    "            return l1\r\n",
    "        rst = []\r\n",
    "        while l1 or l2:\r\n",
    "            rst.append((l1 if l1 > l2 else l2).pop(0))\r\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "        def pick_max(nums, k):\n",
    "            drop = len(nums) - k\n",
    "            out = []\n",
    "            for num in nums:\n",
    "                while drop and out and out[-1] < num:\n",
    "                    out.pop()\n",
    "                    drop -= 1\n",
    "                out.append(num)\n",
    "            return out[:k]\n",
    "\n",
    "        def merge(nums1, nums2):\n",
    "            return [max(nums1, nums2).pop(0) for _ in nums1 + nums2]\n",
    "\n",
    "        return max(merge(pick_max(nums1, i), pick_max(nums2, k - i))\n",
    "                   for i in range(k + 1)\n",
    "                   if i <= len(nums1) and k - i <= len(nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 通过时间20m，注意边界条件，强制删除m个数字，如果单调栈里数字过多，需要从栈顶强制删除\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        ans = []\n",
    "        def getlist(slist, n):\n",
    "            stack = []\n",
    "            m = len(slist) - n\n",
    "            for item in slist:\n",
    "                while stack and m and stack[-1] < item:\n",
    "                    stack.pop()\n",
    "                    m -= 1\n",
    "                stack.append(item)\n",
    "            while m:\n",
    "                stack.pop()\n",
    "                m -= 1\n",
    "            return stack\n",
    "        def mergelist(list1, list2):\n",
    "            res = []\n",
    "            while list1 or list2:\n",
    "                biglist = list1 if list1 > list2 else list2\n",
    "                res.append(biglist.pop(0))\n",
    "            return res\n",
    "            \n",
    "        def comparelist(list1, list2):\n",
    "            if list1 > list2:\n",
    "                return list1.copy()\n",
    "            return list2.copy()\n",
    "\n",
    "        for i in range(0, k+1):\n",
    "            j = k-i\n",
    "            if i > m or j > n or j < 0:\n",
    "                continue\n",
    "            list1 = getlist(nums1, i)\n",
    "            list2 = getlist(nums2, j)\n",
    "            merlist = mergelist(list1.copy(), list2.copy())\n",
    "            if len(ans) == 0:\n",
    "                ans = merlist\n",
    "            else:\n",
    "                ans = comparelist(merlist, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Monotonic stack. Time O(k(m + n + k)) Space O(max(m, n, k))\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        res = []\n",
    "        for k1 in range(k + 1):\n",
    "            k2 = k - k1\n",
    "            if not (0 <= k1 <= m and 0 <= k2 <= n):\n",
    "                continue\n",
    "            print(k1, k2)\n",
    "            res1, res2 = self.retainKDigits(nums1, k1), self.retainKDigits(nums2, k2)\n",
    "            print(res1, res2)\n",
    "            res = max(res, self.merge(res1, res2))\n",
    "        return res\n",
    "\n",
    "    def retainKDigits(self, nums, k):\n",
    "        n = len(nums)\n",
    "        drop = n - k\n",
    "        # monotonically decreasing to get max\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            while stack and stack[-1] < num and drop:\n",
    "                stack.pop()\n",
    "                drop -= 1\n",
    "            stack.append(num)\n",
    "        return stack[:k]\n",
    "\n",
    "    def merge(self, nums1, nums2):\n",
    "        res = []\n",
    "        while nums1 or nums2:\n",
    "            bigger = nums1 if nums1 > nums2 else nums2\n",
    "            res.append(bigger.pop(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        if len(nums2) < len(nums1):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "        r = [0] * k\n",
    "        # 假设 ms[x] 为 nums1 长度为x的最大子序列，则 ms[x - 1] 为ms[x]去掉最左边逆序对的子序列\n",
    "        def get_pair(l):\n",
    "            np = []\n",
    "            sta = []\n",
    "            for i in range(len(l)):\n",
    "                while sta and l[i] > l[sta[-1]]:\n",
    "                    np.append(sta.pop())\n",
    "                sta.append(i)\n",
    "            return np + sta[::-1]\n",
    "        np1 = get_pair(nums1)[::-1]\n",
    "        np2 = get_pair(nums2)\n",
    "        from sortedcontainers import SortedList\n",
    "        if len(np1) > k:\n",
    "            np1 = np1[:k]\n",
    "        s1 = SortedList(np1)\n",
    "        if len(np1) < k:\n",
    "            s2 = SortedList(np2[len(np1) - k:])\n",
    "            np2 = np2[:len(np1) - k]\n",
    "        else:\n",
    "            s2 = SortedList()\n",
    "        def merge(s1, s2):\n",
    "            nonlocal r\n",
    "            s1 = [nums1[v] for v in s1]\n",
    "            s2 = [nums2[v] for v in s2]\n",
    "            ans = []\n",
    "            i1 = i2 = st = 0\n",
    "            same = 1\n",
    "            while i1 < len(s1) and i2 < len(s2):\n",
    "                if s1[i1] > s2[i2]:\n",
    "                    ans.append(s1[i1])\n",
    "                    i1 += 1\n",
    "                elif s1[i1] < s2[i2]:\n",
    "                    ans.append(s2[i2])\n",
    "                    i2 += 1\n",
    "                else:\n",
    "                    t1 = s1[i1:] + s2[i2:]\n",
    "                    t2 = s2[i2:] + s1[i1:]\n",
    "                    if t1 > t2:\n",
    "                        ans.append(s1[i1])\n",
    "                        i1 += 1\n",
    "                    else:\n",
    "                        ans.append(s2[i2])\n",
    "                        i2 += 1\n",
    "                if same:\n",
    "                    while st < len(ans):\n",
    "                        if ans[st] < r[st]:\n",
    "                            return\n",
    "                        elif ans[st] > r[st]:\n",
    "                            same = 0\n",
    "                            st = len(ans)\n",
    "                            break\n",
    "                        st += 1\n",
    "            while i1 < len(s1):\n",
    "                ans.append(s1[i1])\n",
    "                i1 += 1\n",
    "            while i2 < len(s2):\n",
    "                ans.append(s2[i2])\n",
    "                i2 += 1\n",
    "            r = max(r, ans)\n",
    "        merge(s1, s2)\n",
    "        while np1 and np2:\n",
    "            s1.remove(np1.pop())\n",
    "            s2.add(np2.pop())\n",
    "            merge(s1, s2)\n",
    "        return r\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def merge(a,b):\n",
    "            res = []\n",
    "            while a or b:\n",
    "                if not a:\n",
    "                    return res + b\n",
    "                if not b:\n",
    "                    return res + a\n",
    "\n",
    "                if a >= b:\n",
    "                    res.append(a.pop(0))\n",
    "                else:\n",
    "                    res.append(b.pop(0))\n",
    "\n",
    "            return res \n",
    "\n",
    "        def helper(m, list1):\n",
    "            n = len(list1)\n",
    "            k = n - m\n",
    "            stack = []\n",
    "            for num in list1:\n",
    "                while stack and k and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    k -= 1\n",
    "                stack.append(num)\n",
    "\n",
    "            return stack[:-k] if k else stack           \n",
    "\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        res = []\n",
    "        for i in range(n1+1):\n",
    "            if i > k:\n",
    "                break\n",
    "            if k - i > n2:\n",
    "                continue\n",
    "\n",
    "            l1 = helper(i, nums1)\n",
    "            l2 = helper(k-i, nums2)\n",
    "            # print(i,k-i,l1,l2)\n",
    "            res.append(merge(l1,l2))\n",
    "\n",
    "        # print(res)\n",
    "\n",
    "        return max(res, key = lambda x: int(\"\".join([str(i) for i in x])))\n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def find(nums, r):\n",
    "            stack = collections.deque()\n",
    "            for num in nums:\n",
    "                while r and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    r -= 1\n",
    "                stack.append(num)\n",
    "            while r:\n",
    "                stack.pop()\n",
    "                r -= 1\n",
    "            return stack\n",
    "        \n",
    "        def merge(A, B):\n",
    "            res = []\n",
    "            while A and B:\n",
    "                bigger = A if A >= B else B\n",
    "                res.append(bigger.popleft())\n",
    "            res += A if A >= B else B\n",
    "            return res\n",
    "                    \n",
    "\n",
    "        remove = len(nums1) + len(nums2) - k\n",
    "        r_max = min(remove, len(nums1))\n",
    "        r_min = max(0, remove - len(nums2))\n",
    "\n",
    "        return max([merge(find(nums1, r), find(nums2, remove-r)) for r in range(r_min, r_max+1)])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def find(nums, r):\n",
    "            stack = collections.deque()\n",
    "            for num in nums:\n",
    "                while r and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    r -= 1\n",
    "                stack.append(num)\n",
    "            while r:\n",
    "                stack.pop()\n",
    "                r -= 1\n",
    "            return stack\n",
    "        \n",
    "        def merge(A, B):\n",
    "            res = []\n",
    "            while A and B:\n",
    "                bigger = A if A >= B else B\n",
    "                res.append(bigger.popleft())\n",
    "            res += A if A >= B else B\n",
    "            return res\n",
    "                    \n",
    "\n",
    "        remove = len(nums1) + len(nums2) - k\n",
    "        r_max = min(remove, len(nums1))\n",
    "        r_min = max(0, remove - len(nums2))\n",
    "\n",
    "        return max([merge(find(nums1, r), find(nums2, remove-r)) for r in range(r_min, r_max+1)])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def find(nums, r):\n",
    "            stack = []\n",
    "            for num in nums:\n",
    "                while r and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    r -= 1\n",
    "                stack.append(num)\n",
    "            while r:\n",
    "                stack.pop()\n",
    "                r -= 1\n",
    "            return stack\n",
    "        \n",
    "        def merge(A, B):\n",
    "            i, j = 0, 0\n",
    "            res = []\n",
    "            while i < len(A) and j < len(B):\n",
    "                if A[i:] > B[j:]:\n",
    "                    res.append(A[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(B[j])\n",
    "                    j += 1\n",
    "            if i < len(A): res.extend(A[i:])\n",
    "            elif j < len(B): res.extend(B[j:])\n",
    "            return res\n",
    "                    \n",
    "\n",
    "        # ans = []\n",
    "        remove = len(nums1) + len(nums2) - k\n",
    "        # for r in range(min(remove, len(nums1))+1):\n",
    "        #     if remove - r <= len(nums2):\n",
    "        #         res1 = find(nums1, r)\n",
    "        #         res2 = find(nums2, remove - r)\n",
    "        #         res = merge(res1, res2)\n",
    "        #         ans.append(res)\n",
    "        # return max(ans)\n",
    "\n",
    "        return max([merge(find(nums1, r), find(nums2, remove-r)) for r in range(remove+1) if r <= len(nums1) and remove-r <= len(nums2)])\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def fun1(n,k):#返回值一定要是集合\n",
    "            if k==0:\n",
    "                return []\n",
    "            if k==1:\n",
    "                return [max(n)]\n",
    "            stack=[]\n",
    "            for i in n[::-1]:\n",
    "                if len(stack)<k:\n",
    "                    stack=[i]+stack\n",
    "                else:\n",
    "                    if i>=stack[0]:\n",
    "                        t=0\n",
    "                        for j in range(len(stack)-1):\n",
    "                            if stack[j]<stack[j+1]:\n",
    "                                stack=[i]+stack[0:j]+stack[j+1:len(stack)]\n",
    "                                t=1\n",
    "                                break\n",
    "                        if t==0:\n",
    "                            stack.pop()\n",
    "                            stack=[i]+stack\n",
    "            return stack\n",
    "        ##################################################\n",
    "        def fun2(n1,n2):\n",
    "            stack=[]\n",
    "            x1=0\n",
    "            x2=0\n",
    "            while x1<len(n1) and x2<len(n2):\n",
    "                if n1[x1]>n2[x2]:\n",
    "                    stack.append(n1[x1])\n",
    "                    x1+=1\n",
    "                elif n1[x1]==n2[x2]:\n",
    "                    if n1[x1+1:len(n1)]>=n2[x2+1:len(n2)]:\n",
    "                        stack.append(n1[x1])\n",
    "                        x1+=1\n",
    "                    else:\n",
    "                        stack.append(n2[x2])\n",
    "                        x2+=1\n",
    "                else:\n",
    "                    stack.append(n2[x2])\n",
    "                    x2+=1\n",
    "            stack+=n1[x1:len(n1)]\n",
    "            stack+=n2[x2:len(n2)]\n",
    "            return stack\n",
    "        ###############################################\n",
    "        res=[]\n",
    "        for i in range(k+1):\n",
    "            if i<=len(nums1) and k-i<=len(nums2):\n",
    "                res.append(fun2(fun1(nums1,i),fun1(nums2,k-i)))\n",
    "                print(fun2(fun1(nums1,i),fun1(nums2,k-i)),fun1(nums1,i),fun1(nums2,k-i))\n",
    "        return max(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def removeKdigits(num, k: int):\n",
    "            n = len(num)\n",
    "            if k >= n:\n",
    "                return num\n",
    "\n",
    "            stack = []\n",
    "            new_num = []\n",
    "            remove_k = n - k\n",
    "            for c in num:\n",
    "\n",
    "                while remove_k > 0 and stack and c > stack[-1]:\n",
    "                    stack.pop()\n",
    "                    remove_k -= 1\n",
    "\n",
    "                stack.append(c)\n",
    "\n",
    "            if remove_k != 0:\n",
    "                stack = stack[:-remove_k]\n",
    "            \n",
    "            return stack\n",
    "\n",
    "        def merge(nums1, nums2):\n",
    "            ret = []\n",
    "            n1 = len(nums1)\n",
    "            n2 = len(nums2)\n",
    "            i, j = 0, 0\n",
    "\n",
    "            while (i <= n1 - 1 and j <= n2 - 1):\n",
    "                if nums1[i:] >= nums2[j:]:\n",
    "                    ret.append(nums1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ret.append(nums2[j])\n",
    "                    j += 1\n",
    "            \n",
    "            # 判断哪个数组还有剩余\n",
    "            if i <= n1 - 1:\n",
    "                nums = nums1[i:]\n",
    "            else:\n",
    "                nums = nums2[j:]\n",
    "            for num in nums:\n",
    "                ret.append(num)\n",
    "\n",
    "            if len(ret) < k:\n",
    "                return []\n",
    "\n",
    "            return ret\n",
    "            # while(nums1 and nums2):\n",
    "            #     if nums1 > nums2:\n",
    "            #         ret.append(nums1[0]) \n",
    "            #         nums1 = nums1[1:]\n",
    "            #     else:\n",
    "            #         ret.append(nums2[0])\n",
    "            #         nums2 = nums2[1:]\n",
    "                \n",
    "        a = removeKdigits(nums1, 2)\n",
    "        b = removeKdigits(nums2, 3)\n",
    "        # print(removeKdigits(nums1, 2), removeKdigits(nums2, 3))\n",
    "        # print(merge(a, b))\n",
    "        result = []\n",
    "        for i in range(k + 1):\n",
    "            result.append(merge(removeKdigits(nums1, i), removeKdigits(nums2, k-i)))\n",
    "        \n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def find(nums, r):\n",
    "            stack = []\n",
    "            for num in nums:\n",
    "                while r and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    r -= 1\n",
    "                stack.append(num)\n",
    "            while r:\n",
    "                stack.pop()\n",
    "                r -= 1\n",
    "            return stack\n",
    "        \n",
    "        def merge(A, B):\n",
    "            i, j = 0, 0\n",
    "            res = []\n",
    "            while i < len(A) and j < len(B):\n",
    "                if A[i:] > B[j:]:\n",
    "                    res.append(A[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(B[j])\n",
    "                    j += 1\n",
    "            if i < len(A): res.extend(A[i:])\n",
    "            elif j < len(B): res.extend(B[j:])\n",
    "            return res\n",
    "                    \n",
    "\n",
    "        remove = len(nums1) + len(nums2) - k\n",
    "        r_max = min(remove, len(nums1))\n",
    "        r_min = max(0, remove - len(nums2))\n",
    "\n",
    "\n",
    "        return max([merge(find(nums1, r), find(nums2, remove-r)) for r in range(r_min, r_max+1)])\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        if len(nums1) + len(nums2) == k:\n",
    "            return self.merge_two_nums(nums1, nums2)\n",
    "        max_len1 = k if k < len(nums1) else len(nums1)\n",
    "        max_len2 = k if k < len(nums2) else len(nums2)\n",
    "        min_len1 = k - max_len2\n",
    "        min_len2 = k - max_len1\n",
    "        largest_sub_dp1 = self.get_largest_for_range_of_length(nums1, min_len1, max_len1)\n",
    "        largest_sub_dp2 = self.get_largest_for_range_of_length(nums2, min_len2, max_len2)\n",
    "        return max(self.merge_two_nums(largest_sub1, largest_sub_dp2[k - len1]) for len1, largest_sub1 in largest_sub_dp1.items())\n",
    "\n",
    "    @classmethod\n",
    "    def merge_two_nums(cls, nums1, nums2):\n",
    "        if len(nums1) == 0:\n",
    "            return nums2\n",
    "        if len(nums2) == 0:\n",
    "            return nums1\n",
    "        res = [None] * (len(nums1) + len(nums2))\n",
    "        idx_res, idx1, idx2 = 0, 0, 0\n",
    "        while idx1 < len(nums1) and idx2 < len(nums2):\n",
    "            if nums1[idx1:] > nums2[idx2:]:\n",
    "                res[idx_res] = nums1[idx1]\n",
    "                idx1 += 1\n",
    "            else:\n",
    "                res[idx_res] = nums2[idx2]\n",
    "                idx2 += 1\n",
    "            idx_res += 1\n",
    "        if idx1 < len(nums1):\n",
    "            res[idx_res:] = nums1[idx1:]\n",
    "        elif idx2 < len(nums2):\n",
    "            res[idx_res:] = nums2[idx2:]\n",
    "        return res\n",
    "\n",
    "    @classmethod\n",
    "    def get_largest_for_range_of_length(cls, nums, min_len, max_len):\n",
    "        res = {}\n",
    "        to_remove_count_min, to_remove_count_max, removed_count = len(nums) - max_len, len(nums) - min_len, 0\n",
    "        if to_remove_count_min == 0:\n",
    "            res[len(nums)] = nums[:]\n",
    "        if to_remove_count_max == 0:\n",
    "            return res\n",
    "        if to_remove_count_max == len(nums):\n",
    "            res[0] = []\n",
    "            to_remove_count_max -= 1\n",
    "        prefix_stack = [None] * len(nums)\n",
    "        stack_top = -1\n",
    "        for idx, n in enumerate(nums):\n",
    "            while stack_top >= 0 and prefix_stack[stack_top] < n:\n",
    "                removed_count += 1\n",
    "                stack_top -= 1\n",
    "                if removed_count >= to_remove_count_min:\n",
    "                    res[len(nums) - removed_count] = prefix_stack[:stack_top + 1] + nums[idx:]\n",
    "                    if removed_count >= to_remove_count_max:\n",
    "                        return res\n",
    "            stack_top += 1\n",
    "            prefix_stack[stack_top] = n\n",
    "\n",
    "        if removed_count < to_remove_count_min:\n",
    "            stack_top -= (to_remove_count_min - 1 - removed_count)\n",
    "            removed_count = to_remove_count_min - 1\n",
    "        while removed_count < to_remove_count_max:\n",
    "            stack_top -= 1\n",
    "            removed_count += 1\n",
    "            res[len(nums) - removed_count] = prefix_stack[:stack_top + 1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def getNMax(nums,n):\n",
    "            #n是需要保留的个数\n",
    "            stack=[]\n",
    "            k=len(nums)-n\n",
    "            for c in nums:\n",
    "                while stack and k and stack[-1]<c:\n",
    "                    stack.pop()\n",
    "                    k-=1\n",
    "                stack.append(c)\n",
    "            return stack[:n]\n",
    "        def merge(l1,l2):\n",
    "            ans=[]\n",
    "            while l1 and l2:\n",
    "                bigger=l1 if l1>l2 else l2\n",
    "                ans.append(bigger[0])\n",
    "                bigger.pop(0)\n",
    "            if l1:\n",
    "                ans.extend(l1)\n",
    "            if l2:\n",
    "                ans.extend(l2)\n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        #问题转换为分别从nums1中挑选看k1个数形成最大A，从nums2中挑选k2个数形成最大B，将A和B数组组成最大的数\n",
    "        n1,n2=len(nums1),len(nums2)\n",
    "        ret=[]\n",
    "        for i in range(n1+1):\n",
    "            for j in range(n2+1):\n",
    "                if i+j!=k:\n",
    "                    continue\n",
    "                else:\n",
    "                    x=getNMax(nums1,i)\n",
    "                    y=getNMax(nums2,j)\n",
    "                    tmp=merge(x,y)\n",
    "                    ret.append(tmp)\n",
    "\n",
    "           \n",
    "            \n",
    "        return max(ret)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def get_max_list(nums,k):\n",
    "            stack = []\n",
    "            de = len(nums)-k\n",
    "            for i,x in enumerate(nums):\n",
    "                if de==0:\n",
    "                    stack.extend(nums[i:])\n",
    "                    break\n",
    "                while stack and stack[-1]<x and de>0:\n",
    "                    de-=1\n",
    "                    stack.pop()\n",
    "                stack.append(x)\n",
    "            return stack[:k]\n",
    "        def merge(l1,l2):\n",
    "            l1 = deque(l1)\n",
    "            l2 = deque(l2)\n",
    "            nums = []\n",
    "            while l1 and l2:\n",
    "                if l1>l2:\n",
    "                    nums.append(l1.popleft())\n",
    "                else:\n",
    "                    nums.append(l2.popleft())\n",
    "            rest = l1 if l1 else l2\n",
    "            nums.extend(rest)\n",
    "            return nums\n",
    "\n",
    "        ans = []\n",
    "        len1 = len(nums1)\n",
    "        len2 = len(nums2)\n",
    "        for i in range(k+1):\n",
    "            if i<=len1 and k-i<=len2:\n",
    "                x = get_max_list(nums1,i)\n",
    "                y = get_max_list(nums2,k-i)\n",
    "                # print(nums1)\n",
    "                # print(nums2)\n",
    "                # print('i: '+str(i)+'   k-i: '+str(k-i))\n",
    "                # print(x)\n",
    "                # print(y)\n",
    "                # print('---')\n",
    "                ans.append(merge(x,y))\n",
    "        for i in ans:\n",
    "            print(i)\n",
    "        return max(ans)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        max_lst1 = []\n",
    "        n1 = len(nums1)\n",
    "        prev = [0 for _ in range(n1 + 1)]\n",
    "        curr = [0 for _ in range(n1 + 1)]\n",
    "        for i in range(min(k, n1)):\n",
    "            for j in range(1, n1 + 1):\n",
    "                curr[j] = max(curr[j - 1], prev[j - 1] * 10 + nums1[j - 1])\n",
    "            max_lst1.append(curr[-1])\n",
    "            prev = curr\n",
    "            curr = [0 for _ in range(n1 + 1)]\n",
    "\n",
    "        max_lst2 = []\n",
    "        n2 = len(nums2)\n",
    "        prev = [0 for _ in range(n2 + 1)]\n",
    "        curr = [0 for _ in range(n2 + 1)]\n",
    "        for i in range(min(k, n2)):\n",
    "            for j in range(1, n2 + 1):\n",
    "                curr[j] = max(curr[j - 1], prev[j - 1] * 10 + nums2[j - 1])\n",
    "            max_lst2.append(curr[-1])\n",
    "            prev = curr\n",
    "            curr = [0 for _ in range(n2 + 1)]\n",
    "\n",
    "        def merge(num1, num2):\n",
    "            num1 = list(str(num1))\n",
    "            num2 = list(str(num2))\n",
    "            i = 0\n",
    "            j = 0\n",
    "            ans = ''\n",
    "            while i < len(num1) and j < len(num2):\n",
    "                if num1[i] > num2[j]:\n",
    "                    ans += num1[i]\n",
    "                    i += 1\n",
    "                elif num1[i] < num2[j]:\n",
    "                    ans += num2[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    k = 1\n",
    "                    while i + k < len(num1) and j + k < len(num2) and num1[i + k] == num2[j + k]:\n",
    "                        k += 1\n",
    "                    if j + k == len(num2):\n",
    "                        ans += ''.join(num1[i:i + k])\n",
    "                        i += k\n",
    "                    elif i + k == len(num1):\n",
    "                        ans += num2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        if num1[i + k] > num2[j + k]:\n",
    "                            ans += num1[i]\n",
    "                            i += 1\n",
    "                        else:\n",
    "                            ans += num2[j]\n",
    "                            j += 1\n",
    "            while i != len(num1):\n",
    "                ans += num1[i]\n",
    "                i += 1\n",
    "            while j != len(num2):\n",
    "                ans += num2[j]\n",
    "                j += 1\n",
    "            return int(ans)\n",
    "\n",
    "        if len(max_lst1) > len(max_lst2):\n",
    "            max_lst1, max_lst2 = max_lst2, max_lst1\n",
    "        ans = max_lst1[min(len(max_lst1), k) - 1]\n",
    "        ans = max(ans, max_lst2[min(len(max_lst2), k) - 1])\n",
    "        for i in range(max(1, k-len(max_lst2)), min(len(max_lst1) + 1, k)):\n",
    "            max_it = merge(max_lst1[i - 1], max_lst2[k - i - 1])\n",
    "            if max_it > ans:\n",
    "                ans = max_it\n",
    "\n",
    "        return [int(x) for x in str(ans)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def genList(n, nums):\n",
    "            res = []\n",
    "            for i in range(len(nums)):\n",
    "                # 单调栈\n",
    "                while res and nums[i] > res[-1] and len(nums) - i - 1 >= n - len(res):\n",
    "                    res.pop()\n",
    "                if len(res) < n:\n",
    "                    res.append(nums[i])\n",
    "            return res\n",
    "\n",
    "        def merge(l1, l2):\n",
    "            i1, i2, res = 0, 0, []\n",
    "            while i1 < len(l1) and i2 < len(l2):\n",
    "                # 比较的是列表，不是元素\n",
    "                if l1[i1:] >= l2[i2:]:\n",
    "                    res.append(l1[i1])\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    res.append(l2[i2])\n",
    "                    i2 += 1\n",
    "            return res + l1[i1:] + l2[i2:]\n",
    "\n",
    "        return max([\n",
    "            merge(genList(i, nums1), genList(k - i, nums2)) \\\n",
    "            for i in range(max(k - len(nums2), 0), min(len(nums1), k) + 1)\n",
    "        ])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def genList(n, nums):\n",
    "            res = []\n",
    "            for i in range(len(nums)):\n",
    "                while res and nums[i] > res[-1] and len(nums) - i - 1 >= n - len(res):\n",
    "                    res.pop()\n",
    "                if len(res) < n:\n",
    "                    res.append(nums[i])\n",
    "            return res\n",
    "\n",
    "        def merge(l1, l2):\n",
    "            i1, i2, res = 0, 0, []\n",
    "            while i1 < len(l1) and i2 < len(l2):\n",
    "                if l1[i1:] >= l2[i2:]:\n",
    "                    res.append(l1[i1])\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    res.append(l2[i2])\n",
    "                    i2 += 1\n",
    "            return res + l1[i1:] + l2[i2:]\n",
    "\n",
    "\n",
    "        \n",
    "        for i in range(max(k - len(nums2), 0), min(len(nums1), k) + 1):\n",
    "            print(i, '----------')\n",
    "            l1, l2 = genList(i, nums1), genList(k - i, nums2)\n",
    "            print(l1, l2)\n",
    "            print(merge(l1, l2))\n",
    "        \n",
    "\n",
    "        return max([merge(genList(i, nums1), genList(k - i, nums2)) for i in range(max(k - len(nums2), 0), min(len(nums1), k) + 1)])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(nums, a, b):\n",
    "    sub = [[] for _ in range(b - a + 1)]\n",
    "    nums = deque(nums)\n",
    "    st = deque()\n",
    "    while nums:\n",
    "        while st and st[-1] < nums[0]:\n",
    "            i = len(st) + len(nums) - a\n",
    "            if 0 <= i <= b - a:\n",
    "                sub[i] = st + nums\n",
    "            st.pop()\n",
    "        st.append(nums.popleft())\n",
    "    st = list(st)\n",
    "    for i, q in enumerate(sub):\n",
    "        if not q:\n",
    "            sub[i] = deque(st[:i + a])\n",
    "    return sub\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        a, b = max(0, k - n), min(k, m)\n",
    "\n",
    "        subsequence1 = f(nums1, a, b)\n",
    "        subsequence2 = f(nums2, k - b, k - a)\n",
    "\n",
    "        ans = [0] * k\n",
    "        for x, y in zip(subsequence1, subsequence2[::-1]):\n",
    "            tmp = [0] * k\n",
    "            idx = 0\n",
    "            flag = True\n",
    "            while x and y:\n",
    "                tmp[idx] = x.popleft() if x > y else y.popleft()\n",
    "                idx += 1\n",
    "                if tmp[:idx] < ans[:idx]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                tmp = tmp[:idx] + list(x) + list(y)\n",
    "                if tmp > ans:\n",
    "                    ans = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def get_largest_k_digit(k, nums):\n",
    "            stack = []\n",
    "            to_remove = len(nums) - k\n",
    "            for n in nums:\n",
    "                while to_remove and stack and stack[-1] < n:\n",
    "                    stack.pop()\n",
    "                    to_remove -= 1\n",
    "                stack.append(n)\n",
    "            return stack[:k]\n",
    "\n",
    "        res = []\n",
    "        for i in range(k+1):\n",
    "            if i > len(nums1) or k - i > len(nums2):\n",
    "                continue\n",
    "            \n",
    "            stack1 = get_largest_k_digit(i, nums1)\n",
    "            stack2 = get_largest_k_digit(k-i, nums2)\n",
    "            i, j = 0, 0\n",
    "            ans = []\n",
    "            while stack1 or stack2:\n",
    "                bigger = stack1 if stack1 > stack2 else stack2\n",
    "                ans.append(bigger.pop(0))\n",
    "            res.append(ans)\n",
    "\n",
    "        return max(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        arr1 = defaultdict(list)\n",
    "        arr2 = defaultdict(list)\n",
    "\n",
    "        def removeKdigits(nums, k):  # 从nums中取出k个数，使得相对位置不变，且最大\n",
    "            stack = []\n",
    "            drop = len(nums) - k  # 需要去掉这么多数据\n",
    "            for d in nums:\n",
    "                while stack and drop and stack[-1] < d:\n",
    "                    drop -= 1\n",
    "                    stack.pop()\n",
    "                stack.append(d)\n",
    "            return stack[:k]\n",
    "\n",
    "        # def compare(arr1, arr2): # 比较arr1和arr2对应的整数值谁更大\n",
    "        #     return False\n",
    "\n",
    "        def merge(arr1, arr2):  # 按照顺序将arr1和arr2合成最大的数\n",
    "            res = []\n",
    "            while arr1 and arr2:\n",
    "                res.append(arr1.pop(0) if arr1 > arr2 else arr2.pop(0))\n",
    "            res.extend(arr1 or arr2)\n",
    "            return res\n",
    "\n",
    "        for i in range(min(k, len(nums1)) + 1):\n",
    "            arr1[i] = removeKdigits(nums1, i)\n",
    "\n",
    "        for i in range(min(k, len(nums2)) + 1):\n",
    "            arr2[i] = removeKdigits(nums2, i)\n",
    "\n",
    "        # print(arr1, arr2)\n",
    "        ans = [0] * k\n",
    "        for i in range(k + 1):\n",
    "            x = arr1[i][:]\n",
    "            y = arr2[k - i][:]\n",
    "            z = merge(x, y)\n",
    "            if len(z) == k:\n",
    "                # print(ans)\n",
    "                ans = max(ans, z)  # 数组可以直接比较大小...\n",
    "                # print(z, k, ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "nums1 = [6,7]\n",
    "nums2 = [6,0,4]\n",
    "k = 5\n",
    "# [9, 8, 6, 5, 3]\n",
    "c = Solution()\n",
    "print(c.maxNumber(nums1, nums2, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def pick_max(nums, k):\n",
    "            st = []\n",
    "            n = len(nums)\n",
    "            drop = n - k\n",
    "            for num in nums:\n",
    "                while drop and st and st[-1] < num:\n",
    "                    st.pop()\n",
    "                    drop -= 1\n",
    "                st.append(num)\n",
    "            return st[:k]\n",
    "\n",
    "        def merge(A, B):\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "\n",
    "        result = [merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i<=len(nums1) and k-i <= len(nums2)]\n",
    "        return max(result) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "\n",
    "        def pick_max(nums, k):\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while drop and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "\n",
    "        def merge(A, B):\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "        res = []\n",
    "        for i in range(k+1):\n",
    "            if i <= len(nums1) and k-i <= len(nums2):\n",
    "                res.append(merge(pick_max(nums1, i), pick_max(nums2, k-i)))\n",
    "            \n",
    "        return max(res)\n",
    "\n",
    "\n",
    "\n",
    "        return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        merged_list=[]\n",
    "        for i in range(k+1):\n",
    "            if i<=len(nums1) and k-i<=len(nums2):\n",
    "                nums1_temp=self.max_k_nums(i, nums1)\n",
    "                nums2_temp=self.max_k_nums(k-i, nums2)\n",
    "                merged_list.append(self.merge_two_list(nums1_temp, nums2_temp))\n",
    "        return max(merged_list)\n",
    "\n",
    "    def merge_two_list(self,A,B):\n",
    "        # merged_list=[]\n",
    "        # index=0\n",
    "        # while nums1 or nums2:\n",
    "        #     max_num=max(nums1,nums2)\n",
    "        #     merged_list.append(max_num)\n",
    "        #     if nums1[index]==max_num:\n",
    "        #         nums1.pop(0)\n",
    "        #     else:\n",
    "        #         nums2.pop(0)\n",
    "        # # merged_list+=nums1+nums2\n",
    "        ans = []\n",
    "        while A or B:\n",
    "            #[6,7] > [6,0,4] 比较首位字母谁大，如果相同，则继续向后比较直到不相同为止\n",
    "            bigger = A if A > B else B\n",
    "            ans.append(bigger[0])\n",
    "            bigger.pop(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    \n",
    "    def max_k_nums(self,k,nums):\n",
    "        stack=[]\n",
    "        drop=len(nums)-k\n",
    "        for num in nums:\n",
    "            while drop and stack and stack[-1]<num:\n",
    "                stack.pop()\n",
    "                drop-=1\n",
    "            stack.append(num)\n",
    "        return stack[:k]\n",
    "    \n",
    "\n",
    "\n",
    "    def pick_max(nums, k):\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while drop and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "\n",
    "        # def merge(A, B):\n",
    "        #     ans = []\n",
    "        #     while A or B:\n",
    "        #         #[6,7] > [6,0,4] 比较首位字母谁大，如果相同，则继续向后比较直到不相同为止\n",
    "        #         bigger = A if A > B else B\n",
    "        #         ans.append(bigger[0])\n",
    "        #         bigger.pop(0)\n",
    "        #     return ans\n",
    "\n",
    "\n",
    "        # return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "\n",
    "        def pick_max(nums, k):\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while drop and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "\n",
    "        def merge(A, B):\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger[0])\n",
    "                bigger.pop(0)\n",
    "            return ans\n",
    "        \n",
    "        res = []\n",
    "        for i in range(k+1):\n",
    "            if i <= len(nums1) and k-i <= len(nums2):\n",
    "                res.append(merge(pick_max(nums1, i), pick_max(nums2, k-i)))\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def merge(A, B):\n",
    "            res = []\n",
    "            while A or B:\n",
    "                bigger = A if A >= B else B\n",
    "                res.append(bigger.pop(0))\n",
    "            return res\n",
    "\n",
    "        def pick_max(cur, nums):\n",
    "            cur = len(nums) - cur\n",
    "            if cur == len(nums):\n",
    "                return []\n",
    "            stack = []\n",
    "            for d in nums:\n",
    "                while stack and cur > 0 and stack[-1]<d:\n",
    "                    stack.pop()\n",
    "                    cur -= 1\n",
    "                stack.append(d)\n",
    "            if cur > 0:\n",
    "                stack = stack[:-cur]\n",
    "            return stack\n",
    "\n",
    "        return max([merge(pick_max(k1, nums1), pick_max(k-k1, nums2)) for k1 in range(k+1) if k1<=len(nums1) and k-k1<=len(nums2)])\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def combine(lst1, lst2):\n",
    "    if not lst1 or not lst2:\n",
    "        return lst1 + lst2\n",
    "    lst = []\n",
    "    i , j = 0, 0\n",
    "    while i < len(lst1) and j < len(lst2):\n",
    "        if lst1[i] > lst2[j]:\n",
    "            lst.append(lst1[i])\n",
    "            i += 1\n",
    "        elif lst1[i] < lst2[j]:\n",
    "            lst.append(lst2[j])\n",
    "            j += 1\n",
    "        else:\n",
    "            lst.append(lst1[i])\n",
    "            if lst1[i+1:]>lst2[j+1:]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "    if i == len(lst1):\n",
    "        # print(88)\n",
    "        lst += lst2[j:]\n",
    "    if j == len(lst2):\n",
    "        # print(55)\n",
    "        lst += lst1[i:]\n",
    "    return lst\n",
    "\n",
    "def getmax(lst, k):\n",
    "    if k == 0: return []\n",
    "    if k == 1:\n",
    "        return [max(lst)]\n",
    "    index_, max_ = max_index(lst, len(lst)-k+1)\n",
    "    lst = [max_] + getmax(lst[index_+1:], k-1)\n",
    "    return lst\n",
    "\n",
    "\n",
    "def max_index(lst, k):\n",
    "    max_ = -1\n",
    "    for i in range(k):\n",
    "        if lst[i] > max_:\n",
    "            maxi = i\n",
    "            max_ = lst[i]\n",
    "    return maxi, max_\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        length1 = len(nums1)\n",
    "        length2 = len(nums2)\n",
    "        lst = [0] * k\n",
    "        for i in range(min(k,len(nums1))+1):\n",
    "            if i > length1 or k - i > length2:\n",
    "                continue\n",
    "            lst1 = getmax(nums1, i)\n",
    "            # print(lst1)\n",
    "            lst2 = getmax(nums2, k - i)\n",
    "            # print(lst2)\n",
    "            lst = max(lst, combine(lst1, lst2))\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import  functools\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k: int):\n",
    "\n",
    "        # 单调栈\n",
    "        def helper1(numbers,kk):\n",
    "            stack = []\n",
    "            kk_back = kk\n",
    "            for i in range(len(numbers)):\n",
    "                ele = numbers[i]\n",
    "                if not stack:\n",
    "                    stack.append(ele)\n",
    "                    kk-=1\n",
    "                else:\n",
    "                    while stack and ele>stack[-1]:\n",
    "                        if len(numbers)-i>=kk+1:\n",
    "                            stack.pop()\n",
    "                            kk+=1\n",
    "                        else:\n",
    "                            break\n",
    "                    stack.append(ele)\n",
    "                    kk-=1\n",
    "            return stack[:kk_back]\n",
    "\n",
    "        # def helper1(nums, k):\n",
    "        #     stack = []\n",
    "        #     drop = len(nums) - k\n",
    "        #     for num in nums:\n",
    "        #         while drop and stack and stack[-1] < num:\n",
    "        #             stack.pop()\n",
    "        #             drop -= 1\n",
    "        #         stack.append(num)\n",
    "        #     return stack[:k]\n",
    "\n",
    "        def merge(A, B):\n",
    "            ans = []\n",
    "            # print(A,B)\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "        # def merge(n1,n2):\n",
    "        #     res = []\n",
    "        #     i,j=0,0\n",
    "        #     while i<len(n1) and j<len(n2):\n",
    "        #         if n1[i]<n2[j]:\n",
    "        #             res.append(n2[j])\n",
    "        #             j+=1\n",
    "        #         elif n1[i]>n2[j]:\n",
    "        #             res.append(n1[i])\n",
    "        #             i+=1\n",
    "        #         else:\n",
    "        #             res.append(n1[i])\n",
    "        #             res1 = merge(n1[i+1:],n2[j:])\n",
    "        #             res2 = merge(n1[i:],n2[j+1:])\n",
    "        #             res+=max(res1,res2)\n",
    "        #             return res\n",
    "        #     while i<len(n1):\n",
    "        #         res.append(n1[i])\n",
    "        #         i+=1\n",
    "        #     while j<len(n2):\n",
    "        #         res.append(n2[j])\n",
    "        #         j+=1\n",
    "        #     return res\n",
    "\n",
    "        ress = []\n",
    "        for i in range(len(nums1)+1):\n",
    "            if k-i>len(nums2):\n",
    "                continue\n",
    "            if k-i<0:\n",
    "                break\n",
    "            res1 = helper1(nums1,i)\n",
    "            res2 = helper1(nums2,k-i)\n",
    "            # if i>14:\n",
    "            #     print(len(res1),len(res2),i,k-i)\n",
    "            ress.append(merge(res1,res2))\n",
    "            # print(ress[i-1])\n",
    "        ress.sort()\n",
    "        # print(len(ress[-1]))\n",
    "        return ress[-1]\n",
    "\n",
    "        return []\n",
    "                \n",
    "\n",
    "\n",
    "        # 单调栈。。。。我是傻逼\n",
    "        result = []\n",
    "        i,j=0,0\n",
    "        flag = -1\n",
    "        while i<len(nums1) and j<len(nums2):\n",
    "            if k==0:\n",
    "                break\n",
    "            if nums1[i]<nums2[j]:\n",
    "                result.append([nums2[j],1])\n",
    "                k-=1\n",
    "                j+=1\n",
    "                flag = -1\n",
    "            elif nums1[i]>nums2[j]:\n",
    "                result.append([nums1[i],0])\n",
    "                k-=1\n",
    "                i+=1\n",
    "                flag = -1\n",
    "            else:\n",
    "                if flag!=-1:\n",
    "                    if flag==0:\n",
    "                        result.append([nums1[i],0])\n",
    "                        k-=1\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        result.append([nums2[j],1])\n",
    "                        k-=1\n",
    "                        j+=1\n",
    "                else:\n",
    "                    temp_i,temp_j = i+1,j+1\n",
    "                    while temp_i<len(nums1) and temp_j<len(nums2):\n",
    "                        if nums1[temp_i]<nums2[temp_j]:\n",
    "                            flag = 1\n",
    "                            break\n",
    "                        if nums1[temp_i]>nums2[temp_j]:\n",
    "                            flag=0\n",
    "                            break\n",
    "                        temp_i+=1\n",
    "                        temp_j+=1\n",
    "                    if flag==-1:\n",
    "                        while temp_i<len(nums1) and nums1[temp_i]==nums1[i]:\n",
    "                            temp_i+=1\n",
    "                        while temp_j<len(nums2) and nums2[temp_j]==nums2[j]:\n",
    "                            temp_j+=1\n",
    "                        if temp_i>=len(nums1) and temp_j>=len(nums2):\n",
    "                            flag = 0\n",
    "                        elif temp_i>=len(nums1):\n",
    "                            if nums2[temp_j]<nums1[i]:\n",
    "                                flag=0\n",
    "                            else:\n",
    "                                flag=1\n",
    "                        elif temp_j>=len(nums2):\n",
    "                            if nums1[temp_i]<nums1[i]:\n",
    "                                flag=1\n",
    "                            else:\n",
    "                                flag=0\n",
    "        print(result)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 自己思考\n",
    "        # 这题很麻烦，想了很久。两个数组各自排序降序，带上坐标。先取两个数组中最大的那个，取完后那个数组左边就不能用了，如果此时两个数组剩下的个数加起来不到 k-1，则我们只能取第二大，以此类推。边界判断很麻烦，试下用递归。\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            nums1[i] = [nums1[i], i]\n",
    "        for i in range(len(nums2)):\n",
    "            nums2[i] = [nums2[i], i]\n",
    "\n",
    "        def compare(a,b):\n",
    "            if a[0]<b[0]:\n",
    "                return 1\n",
    "            if a[0]>b[0]:\n",
    "                return -1\n",
    "            if a[1]<b[1]:\n",
    "                return -1\n",
    "            if a[1]>b[1]:\n",
    "                return 1\n",
    "            return 0\n",
    "\n",
    "        # nums1.sort(reverse=True)\n",
    "        # nums2.sort(reverse=True)\n",
    "        nums1.sort(key=functools.cmp_to_key(compare))\n",
    "        nums2.sort(key=functools.cmp_to_key(compare))\n",
    "\n",
    "        result = []\n",
    "        min_index1, min_index2 = -1, -1  # 是-1不是0，因为是 len(nums)-1-min_index，如果初始值是0会少一个\n",
    "        len_nums1, len_nums2 = len(nums1), len(nums2)\n",
    "\n",
    "        def recurr(i, j):\n",
    "            nonlocal min_index1, min_index2, k\n",
    "            nonlocal len_nums1, len_nums2\n",
    "            if k == 0:\n",
    "                return\n",
    "            while i < len(nums1) and nums1[i][1] < min_index1:\n",
    "                # i += 1\n",
    "                del nums1[i]\n",
    "            while j < len(nums2) and nums2[j][1] < min_index2:\n",
    "                # j += 1\n",
    "                del nums2[j]\n",
    "            if i == len(nums1):\n",
    "                if len_nums2 - 1 - nums2[j][1] + len_nums1 - 1 - min_index1 < k - 1:\n",
    "                    recurr(i, j + 1)\n",
    "                else:\n",
    "                    result.append(nums2[j][0])\n",
    "                    k -= 1\n",
    "                    min_index2 = nums2[j][1]\n",
    "                    del nums2[j]\n",
    "                    recurr(i, 0)\n",
    "            elif j == len(nums2):\n",
    "                if len_nums1 - 1 - nums1[i][1] + len_nums2 - 1 - min_index2 < k - 1:\n",
    "                    recurr(i + 1, j)\n",
    "                else:\n",
    "                    result.append(nums1[i][0])\n",
    "                    k -= 1\n",
    "                    min_index1 = nums1[i][1]\n",
    "                    del nums1[i]\n",
    "                    recurr(0, j)\n",
    "            elif nums1[i][0] == nums2[j][0]:  # 这块错了超级多细节\n",
    "                temp1 = len_nums1 - 1 - nums1[i][1] + len_nums2 - 1 - min_index2\n",
    "                temp2 = len_nums2 - 1 - nums2[j][1] + len_nums1 - 1 - min_index1\n",
    "                if temp1 >= k - 1 and temp2 < k-1:\n",
    "                    result.append(nums1[i][0])\n",
    "                    k -= 1\n",
    "                    min_index1 = nums1[i][1]\n",
    "                    del nums1[i]\n",
    "                    recurr(0, j)\n",
    "                elif temp2 >= k - 1 and temp1 < k-1:\n",
    "                    result.append(nums2[j][0])\n",
    "                    k -= 1\n",
    "                    min_index2 = nums2[j][1]\n",
    "                    del nums2[j]\n",
    "                    recurr(i, 0)\n",
    "                elif temp1 < k-1 and temp2 < k-1:\n",
    "                    recurr(i + 1, j + 1)\n",
    "                else:\n",
    "                    if i==0 and j==0:\n",
    "                        if len(nums1)==1:\n",
    "                            result.append(nums2[j][0])\n",
    "                            k -= 1\n",
    "                            min_index2 = nums2[j][1]\n",
    "                            del nums2[j]\n",
    "                            recurr(i, 0)\n",
    "                        elif len(nums2)==1:\n",
    "                            result.append(nums1[i][0])\n",
    "                            k -= 1\n",
    "                            min_index1 = nums1[i][1]\n",
    "                            del nums1[i]\n",
    "                            recurr(0, j)\n",
    "                        else:\n",
    "                            if nums1[1][0]>nums2[1][0]:\n",
    "                                result.append(nums2[j][0])\n",
    "                                k -= 1\n",
    "                                min_index2 = nums2[j][1]\n",
    "                                del nums2[j]\n",
    "                                recurr(i, 0)\n",
    "                            else:\n",
    "                                result.append(nums1[i][0])\n",
    "                                k -= 1\n",
    "                                min_index1 = nums1[i][1]\n",
    "                                del nums1[i]\n",
    "                                recurr(0, j)\n",
    "                    elif i > 0 and j == 0:\n",
    "                        result.append(nums1[i][0])\n",
    "                        k -= 1\n",
    "                        min_index1 = nums1[i][1]\n",
    "                        del nums1[i]\n",
    "                        recurr(0, j)\n",
    "                    elif j > 0 and i == 0:\n",
    "                        result.append(nums2[j][0])\n",
    "                        k -= 1\n",
    "                        min_index2 = nums2[j][1]\n",
    "                        del nums2[j]\n",
    "                        recurr(i, 0)\n",
    "                    else:\n",
    "                        if nums1[0][0] > nums2[0][0]:   # 最后是这里错了，但。。。算了\n",
    "                            result.append(nums1[i][0])\n",
    "                            k -= 1\n",
    "                            min_index1 = nums1[i][1]\n",
    "                            del nums1[i]\n",
    "                            recurr(0, j)\n",
    "                        else:\n",
    "                            result.append(nums2[j][0])\n",
    "                            k -= 1\n",
    "                            min_index2 = nums2[j][1]\n",
    "                            del nums2[j]\n",
    "                            recurr(i, 0)\n",
    "            elif nums1[i][0] > nums2[j][0]:\n",
    "                if len_nums1 - 1 - nums1[i][1] + len_nums2 - 1 - min_index2 >= k - 1:\n",
    "                    result.append(nums1[i][0])\n",
    "                    k -= 1\n",
    "                    min_index1 = nums1[i][1]\n",
    "                    del nums1[i]\n",
    "                    recurr(0, j)\n",
    "                else:\n",
    "                    recurr(i + 1, j)\n",
    "            else:\n",
    "                if len_nums2 - 1 - nums2[j][1] + len_nums1 - 1 - min_index1 >= k - 1:\n",
    "                    result.append(nums2[j][0])\n",
    "                    k -= 1\n",
    "                    min_index2 = nums2[j][1]\n",
    "                    del nums2[j]\n",
    "                    recurr(i, 0)\n",
    "                else:\n",
    "                    recurr(i, j + 1)\n",
    "\n",
    "        recurr(0, 0)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        res = 0\n",
    "\n",
    "        def get_max_l(origin: list, count: int):\n",
    "            stack = []\n",
    "            remain = len(origin)\n",
    "\n",
    "            for i in origin:\n",
    "                while len(stack) > 0 and stack[-1] < i and remain > count - len(stack):\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "                remain -= 1\n",
    "\n",
    "            while len(stack) > count:\n",
    "                stack.pop()\n",
    "            return stack\n",
    "\n",
    "        def compare_max(l1, l2):\n",
    "            for i in range(len(l1)):\n",
    "                if l1[i] > l2[i]:\n",
    "                    return l1\n",
    "                if l1[i] < l2[i]:\n",
    "                    return l2\n",
    "            return l1\n",
    "        temp_res = None\n",
    "        for i in range(k+1):\n",
    "            len1 = i\n",
    "            len2 = k-i\n",
    "            if len1 > len(nums1) or len2 > len(nums2):\n",
    "                continue\n",
    "\n",
    "            res1 = get_max_l(nums1, len1)\n",
    "            res2 = get_max_l(nums2, len2)\n",
    "\n",
    "            def combine_max(l1, l2) -> list:\n",
    "                res = []\n",
    "                if len(l1) == 0:\n",
    "                    return list(l2)\n",
    "                if len(l2) == 0:\n",
    "                    return list(l1)\n",
    "\n",
    "                offset = 0\n",
    "\n",
    "                while True:\n",
    "                    if l1[offset] > l2[offset]:\n",
    "                        res = combine_max(l1[1:], l2)\n",
    "                        res.insert(0, l1[0])\n",
    "                        return res\n",
    "\n",
    "                    if l1[offset] < l2[offset]:\n",
    "                        res = combine_max(l1, l2[1:])\n",
    "                        res.insert(0, l2[0])\n",
    "                        return res\n",
    "\n",
    "                    offset += 1\n",
    "\n",
    "                    if offset == len(l1):\n",
    "                        res = combine_max(l1, l2[1:])\n",
    "                        res.insert(0, l2[0])\n",
    "                        return res\n",
    "                    if offset == len(l2):\n",
    "                        res = combine_max(l1[1:], l2)\n",
    "                        res.insert(0, l1[0])\n",
    "                        return res\n",
    "\n",
    "            if temp_res == None:\n",
    "                temp_res = combine_max(res1, res2)\n",
    "            else:\n",
    "                temp_res = compare_max(temp_res, combine_max(res1, res2))\n",
    "        return temp_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def select(lst, t):\n",
    "            n = len(lst)\n",
    "            stack = []\n",
    "            canDiscard = n - t\n",
    "            for i in range(n):\n",
    "                while stack and stack[-1] < lst[i] and canDiscard:\n",
    "                    stack.pop()\n",
    "                    canDiscard -= 1\n",
    "                stack.append(lst[i])\n",
    "            return stack[:t]\n",
    "\n",
    "        def compare(nums1: List[int], nums2: List[int]) -> int:\n",
    "            m, n = len(nums1), len(nums2)\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                diff = nums1[i] - nums2[j]\n",
    "                if diff != 0:\n",
    "                    return diff\n",
    "                i += 1\n",
    "                j += 1\n",
    "            return (m - i) - (n - j)\n",
    "        \n",
    "        def combine(lst1, lst2):\n",
    "            if not lst1:\n",
    "                return lst2\n",
    "            if not lst2:\n",
    "                return lst1\n",
    "            if compare(lst1, lst2) >= 0:\n",
    "                return [lst1[0]] + combine(lst1[1:], lst2)\n",
    "            return [lst2[0]] + combine(lst1, lst2[1:])\n",
    "\n",
    "        ret = (nums1 + nums2)[:k]\n",
    "\n",
    "        for i in range(k+1):\n",
    "            len1 = i \n",
    "            len2 = k - i \n",
    "            if len1 > len(nums1) or len2 > len(nums2):\n",
    "                continue\n",
    "            lst1 = select(nums1, len1)\n",
    "            lst2 = select(nums2, len2)\n",
    "            temp = combine(lst1, lst2)\n",
    "            ret = max(ret, temp)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k: int):\n",
    "        def generate_one_list(nums, length):\n",
    "            num_stack = []\n",
    "            for idx, num in enumerate(nums):\n",
    "                while num_stack and len(nums) - idx + len(num_stack) - 1 >= length and num_stack[-1] < num:\n",
    "                    num_stack.pop()\n",
    "                num_stack.append(num)\n",
    "            return num_stack[: length]\n",
    "\n",
    "        \n",
    "\n",
    "        def combine_list(list1, list2):\n",
    "            idx1 = 0\n",
    "            idx2 = 0\n",
    "            ret_list = []\n",
    "            while idx1 < len(list1) or idx2 < len(list2):\n",
    "                if idx1 == len(list1):\n",
    "                    ret_list.append(list2[idx2])\n",
    "                    idx2 += 1\n",
    "                elif idx2 == len(list2):\n",
    "                    ret_list.append(list1[idx1])\n",
    "                    idx1 += 1\n",
    "                else:\n",
    "                    if compare(list1, idx1, list2, idx2):\n",
    "                        ret_list.append(list1[idx1])\n",
    "                        idx1 += 1\n",
    "                    else:\n",
    "                        ret_list.append(list2[idx2])\n",
    "                        idx2 += 1\n",
    "            return ret_list\n",
    "\n",
    "        def compare(list1, idx1, list2, idx2):\n",
    "            len1 = len(list1)\n",
    "            len2 = len(list2)\n",
    "\n",
    "            while idx1 < len1 and idx2 < len2:\n",
    "                if list1[idx1] != list2[idx2]:\n",
    "                    return (list1[idx1] - list2[idx2]) > 0\n",
    "                idx1 += 1\n",
    "                idx2 += 1\n",
    "            \n",
    "            return ((len1 - idx1) - (len2 - idx2)) > 0\n",
    "\n",
    "\n",
    "        candidates = []\n",
    "        for len1 in range(k + 1):\n",
    "            len2 = k - len1\n",
    "            if len1 > len(nums1) or len2 > len(nums2):\n",
    "                continue\n",
    "            list1 = generate_one_list(nums1, len1)\n",
    "            list2 = generate_one_list(nums2, len2)\n",
    "            candidates.append(combine_list(list1, list2))\n",
    "\n",
    "        ret_list = sorted(candidates)\n",
    "        return ret_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def getmaxq(nums, n, x):\n",
    "            if x == 0:\n",
    "                return []\n",
    "            elif x == n:\n",
    "                return nums[:]\n",
    "            stk = [0] * x\n",
    "            r = n - x\n",
    "            top = -1\n",
    "            for i in nums:\n",
    "                while top >= 0 and stk[top] < i and r > 0:\n",
    "                    top -= 1\n",
    "                    r -= 1\n",
    "                if top < x - 1:\n",
    "                    # 添加当前数到栈顶\n",
    "                    top += 1\n",
    "                    stk[top] = i\n",
    "                else:\n",
    "                    r -= 1 # 丢掉当前数\n",
    "            return stk\n",
    "        def comp(nm1, l1, i1, nm2, l2, i2):\n",
    "            while i1 < l1 and i2 < l2:\n",
    "                d = nm1[i1] - nm2[i2]\n",
    "                if d != 0:\n",
    "                    return d\n",
    "                i1 += 1\n",
    "                i2 += 1\n",
    "            return (l1 - i1) - (l2 - i2)\n",
    "        def merge(nm1, l1, nm2, l2):\n",
    "            mg = [0] * k\n",
    "            i1 = i2 = 0\n",
    "            for i in range(k):\n",
    "                if comp(nm1, l1, i1, nm2, l2, i2) > 0:\n",
    "                    mg[i] = nm1[i1]\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    mg[i] = nm2[i2]\n",
    "                    i2 += 1\n",
    "            return mg\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        # 假设mq是长度为l的最大子序列，那么长度为l-1的子序列是删除第一个顺序数\n",
    "        def rmnum(mq, l):\n",
    "            for i in range(l - 1):\n",
    "                if mq[i] < mq[i + 1]:\n",
    "                    return mq[:i] + mq[i + 1:]\n",
    "            return mq[:l - 1]\n",
    "        l1, l2 = min(k, m), min(k, n)\n",
    "        mq1 = getmaxq(nums1, m, l1)\n",
    "        mq2 = getmaxq(nums2, n, l2)\n",
    "        mqs1 = [mq1]\n",
    "        mqs2 = [mq2]\n",
    "        while l1 > 0:\n",
    "            mqs1.insert(0, rmnum(mqs1[0], l1))\n",
    "            l1 -= 1\n",
    "        while l2 > 0:\n",
    "            mqs2.insert(0, rmnum(mqs2[0], l2))\n",
    "            l2 -= 1\n",
    "        for x in range(k + 1):\n",
    "            y = k - x\n",
    "            if x <= m and y <= n:\n",
    "                nm1 = mqs1[x]\n",
    "                nm2 = mqs2[y]\n",
    "                mg = merge(nm1, x, nm2, y)\n",
    "                if not ans or comp(mg, k, 0, ans, k, 0) > 0:\n",
    "                    ans = mg\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k: int):\n",
    "        def generate_one_list(nums, length):\n",
    "            num_stack = []\n",
    "            for idx, num in enumerate(nums):\n",
    "                while num_stack and len(nums) - idx + len(num_stack) - 1 >= length and num_stack[-1] < num:\n",
    "                    num_stack.pop()\n",
    "                num_stack.append(num)\n",
    "            return num_stack[: length]\n",
    "\n",
    "        \n",
    "\n",
    "        def combine_list(list1, list2):\n",
    "            idx1 = 0\n",
    "            idx2 = 0\n",
    "            ret_list = []\n",
    "            while idx1 < len(list1) or idx2 < len(list2):\n",
    "                if idx1 == len(list1):\n",
    "                    ret_list.append(list2[idx2])\n",
    "                    idx2 += 1\n",
    "                elif idx2 == len(list2):\n",
    "                    ret_list.append(list1[idx1])\n",
    "                    idx1 += 1\n",
    "                else:\n",
    "                    if compare(list1, idx1, list2, idx2):\n",
    "                        ret_list.append(list1[idx1])\n",
    "                        idx1 += 1\n",
    "                    else:\n",
    "                        ret_list.append(list2[idx2])\n",
    "                        idx2 += 1\n",
    "            return ret_list\n",
    "\n",
    "        def compare(list1, idx1, list2, idx2):\n",
    "            len1 = len(list1)\n",
    "            len2 = len(list2)\n",
    "\n",
    "            while idx1 < len1 and idx2 < len2:\n",
    "                if list1[idx1] != list2[idx2]:\n",
    "                    return (list1[idx1] - list2[idx2]) > 0\n",
    "                idx1 += 1\n",
    "                idx2 += 1\n",
    "            \n",
    "            return ((len1 - idx1) - (len2 - idx2)) > 0\n",
    "\n",
    "\n",
    "        candidates = []\n",
    "        for len1 in range(k + 1):\n",
    "            len2 = k - len1\n",
    "            if len1 > len(nums1) or len2 > len(nums2):\n",
    "                continue\n",
    "            list1 = generate_one_list(nums1, len1)\n",
    "            list2 = generate_one_list(nums2, len2)\n",
    "            candidates.append(combine_list(list1, list2))\n",
    "\n",
    "        ret_list = sorted(candidates)\n",
    "        return ret_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def pick_nums(nums, m):\n",
    "            n = len(nums)\n",
    "            if m == 0:\n",
    "                return []\n",
    "            res = [nums[0]]\n",
    "            m -= 1\n",
    "            for i in range(1,n):\n",
    "                while res and nums[i] > res[-1] and n-i > m:\n",
    "                    res.pop()\n",
    "                    m += 1\n",
    "                if m > 0:\n",
    "                    res.append(nums[i])\n",
    "                    m -= 1\n",
    "                \n",
    "            return res\n",
    "        \n",
    "        def merge(A, B):\n",
    "            res = []\n",
    "            while A and B:\n",
    "                if A > B:\n",
    "                    res.append(A[0])\n",
    "                    A.pop(0)\n",
    "                else:\n",
    "                    res.append(B[0])\n",
    "                    B.pop(0)\n",
    "            if A: res += A\n",
    "            if B: res += B\n",
    "            return res\n",
    "        ans = []\n",
    "        for i in range(k+1):\n",
    "            if i <= len(nums1) and k - i <= len(nums2):\n",
    "                ans.append(merge(pick_nums(nums1, i), pick_nums(nums2, k-i)))\n",
    "\n",
    "        return max(ans)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def getmaxq(nums, n, x):\n",
    "            if x == 0:\n",
    "                return []\n",
    "            elif x == n:\n",
    "                return nums[:]\n",
    "            stk = [0] * x\n",
    "            r = n - x\n",
    "            top = -1\n",
    "            for i in nums:\n",
    "                while top >= 0 and stk[top] < i and r > 0:\n",
    "                    top -= 1\n",
    "                    r -= 1\n",
    "                if top < x - 1:\n",
    "                    # 添加当前数到栈顶\n",
    "                    top += 1\n",
    "                    stk[top] = i\n",
    "                else:\n",
    "                    r -= 1 # 丢掉当前数\n",
    "            return stk\n",
    "        def comp(nm1, l1, i1, nm2, l2, i2):\n",
    "            while i1 < l1 and i2 < l2:\n",
    "                d = nm1[i1] - nm2[i2]\n",
    "                if d != 0:\n",
    "                    return d\n",
    "                i1 += 1\n",
    "                i2 += 1\n",
    "            return (l1 - i1) - (l2 - i2)\n",
    "        def merge(nm1, l1, nm2, l2):\n",
    "            mg = [0] * k\n",
    "            i1 = i2 = 0\n",
    "            for i in range(k):\n",
    "                if comp(nm1, l1, i1, nm2, l2, i2) > 0:\n",
    "                    mg[i] = nm1[i1]\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    mg[i] = nm2[i2]\n",
    "                    i2 += 1\n",
    "            return mg\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = []\n",
    "        # 假设mq是长度为l的最大子序列，那么长度为l-1的子序列是删除第一个顺序数\n",
    "        def rmnum(mq, l):\n",
    "            for i in range(l - 1):\n",
    "                if mq[i] < mq[i + 1]:\n",
    "                    return mq[:i] + mq[i + 1:]\n",
    "            return mq[:l - 1]\n",
    "        l1, l2 = min(k, m), min(k, n)\n",
    "        mq1 = getmaxq(nums1, m, l1)\n",
    "        mq2 = getmaxq(nums2, n, l2)\n",
    "        mqs1 = [mq1]\n",
    "        mqs2 = [mq2]\n",
    "        while l1 > 0:\n",
    "            mqs1.insert(0, rmnum(mqs1[0], l1))\n",
    "            l1 -= 1\n",
    "        while l2 > 0:\n",
    "            mqs2.insert(0, rmnum(mqs2[0], l2))\n",
    "            l2 -= 1\n",
    "        for x in range(k + 1):\n",
    "            y = k - x\n",
    "            if x <= m and y <= n:\n",
    "                nm1 = mqs1[x]\n",
    "                nm2 = mqs2[y]\n",
    "                mg = merge(nm1, x, nm2, y)\n",
    "                if not ans or comp(mg, k, 0, ans, k, 0) > 0:\n",
    "                    ans = mg\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], kk: int) -> List[int]:\n",
    "\n",
    "        def topk(nums, k):\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for c in nums:\n",
    "                while stack and stack[-1] < c and drop > 0:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(c)\n",
    "            return stack[:k]\n",
    "\n",
    "        def merge(list1, list2):\n",
    "            ans = []\n",
    "            while list1 or list2:\n",
    "                bigger = list1 if list1 > list2 else list2\n",
    "                ans.append(bigger.pop(0))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        temp = []\n",
    "        for m in range(kk+1):\n",
    "            if m > len(nums1) or kk - m > len(nums2):\n",
    "                continue\n",
    "\n",
    "            s1 = topk(nums1, m)\n",
    "            s2 = topk(nums2, kk-m)\n",
    "            temp.append(merge(s1, s2))\n",
    "        \n",
    "        return max(temp)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def subnumber(nums,k):\n",
    "            stack=[]\n",
    "            drop=len(nums)-k\n",
    "            for sub in nums:\n",
    "                while stack and drop and stack[-1]<sub:\n",
    "                    stack.pop()\n",
    "                    drop-=1\n",
    "                stack.append(sub)\n",
    "            return stack[:k]\n",
    "        def merge(a,b):\n",
    "            ans=[]\n",
    "            while a or b:\n",
    "                if a>b:\n",
    "                    bigger =a\n",
    "                else:\n",
    "                    bigger=b\n",
    "                ans.append(bigger[0])\n",
    "                bigger.pop(0)  \n",
    "            return ans\n",
    "        result=[]\n",
    "        for i in range(k+1):\n",
    "            mid=merge(subnumber(nums1,i),subnumber(nums2,k-i))\n",
    "            if len(mid)==k:\n",
    "                result.append(merge(subnumber(nums1,i),subnumber(nums2,k-i)))\n",
    "\n",
    "        return max(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def select(nums,k):\n",
    "            res = []\n",
    "            cnt = len(nums)-k\n",
    "            i = 0\n",
    "            while i<len(nums):\n",
    "                while len(res)>0 and nums[i]>res[-1]:\n",
    "                    res.pop()\n",
    "                    cnt-=1\n",
    "                    if cnt == 0:\n",
    "                        break\n",
    "                res.append(nums[i])\n",
    "                i+=1\n",
    "                if cnt==0:\n",
    "                    break\n",
    "            if cnt>0:\n",
    "                for j in range(cnt):\n",
    "                    res.pop()\n",
    "            elif cnt==0:\n",
    "                for j in range(i,len(nums)):\n",
    "                    res.append(nums[j])\n",
    "            return res\n",
    "        \n",
    "        def merge(nums1,nums2):\n",
    "            res = []\n",
    "            m = len(nums1)\n",
    "            n = len(nums2)\n",
    "            while len(res)<m+n:\n",
    "                if nums1>nums2:\n",
    "                    res.append(nums1[0])\n",
    "                    nums1.pop(0)\n",
    "                else:\n",
    "                    res.append(nums2[0])\n",
    "                    nums2.pop(0)\n",
    "            return res\n",
    "\n",
    "        res_li = []\n",
    "\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        for k1 in range(max(0,k-n),min(m,k)+1):\n",
    "            res_li.append(merge(select(nums1,k1),select(nums2,k-k1)))\n",
    "        final_res = res_li[0]\n",
    "        for ele in res_li:\n",
    "            final_res = max(final_res,ele)\n",
    "        return final_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\r\n",
    "        def get_max_num(num, l):\r\n",
    "            res = []\r\n",
    "            l = len(num) - l\r\n",
    "            for n in num:\r\n",
    "                while res and l and n > res[-1]:\r\n",
    "                    res.pop()\r\n",
    "                    l -= 1\r\n",
    "                res.append(n)\r\n",
    "            return res[:len(res) - l]\r\n",
    "        def merge(n1, n2):\r\n",
    "            res = []\r\n",
    "            while n1 or n2:\r\n",
    "                bigger = n1 if n1 > n2 else n2\r\n",
    "                res.append(bigger[0])\r\n",
    "                bigger.pop(0)\r\n",
    "            return res\r\n",
    "        res = []\r\n",
    "        for i in range(0, k +1):\r\n",
    "            if i > len(nums1) or k-i > len(nums2):\r\n",
    "                continue\r\n",
    "            # print(i, k - i)\r\n",
    "            tmp = merge(get_max_num(nums1, i), get_max_num(nums2, k - i))\r\n",
    "            res.append(tmp)\r\n",
    "        # print(res)\r\n",
    "        return max(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        rst = []\n",
    "        for i in range(k + 1):\n",
    "            if i <= len(nums1) and k - i <= len(nums2):\n",
    "                rst.append(self.merge(self.pick_max(nums1, i), self.pick_max(nums2, k - i)))\n",
    "        return max(rst)\n",
    "    \n",
    "    def pick_max(self, nums, k):\n",
    "        st = []\n",
    "        drop = len(nums) - k\n",
    "        for num in nums:\n",
    "            while drop and st and st[-1] < num:\n",
    "                st.pop()\n",
    "                drop -= 1\n",
    "            st.append(num)\n",
    "        return st[:k]\n",
    "    \n",
    "    def merge(self, nums1, nums2):\n",
    "        lst = []\n",
    "        while nums1 or nums2:\n",
    "            bigger = nums1 if nums1 > nums2 else nums2\n",
    "            lst.append(bigger.pop(0))\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def find(nums, k):\n",
    "            n = len(nums)\n",
    "            stack = []\n",
    "            drop = n - k\n",
    "            for i in nums:\n",
    "                while drop > 0 and stack and stack[-1] < i:   # 保留k个元素，则需要删掉n-k个元素\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(i)\n",
    "                # k -= 1\n",
    "            # print(nums[:k])\n",
    "            return stack[:k]   # 注意这里返回的不是nums[:k]，而是stack[:k]\n",
    "        def merge(nums1, nums2):   # merge([6, 7], [6, 0, 4]), 用双指针会返回66704而不是67604\n",
    "                                    # 这是由于不能只判断第一个数字，而是应该判断整个序列（67>60）\n",
    "                                    # (解决方案)另写一个函数判断大小，或者list直接用大于号比较\n",
    "            ans = []\n",
    "            while nums1 or nums2:\n",
    "                bigger = max(nums1, nums2)\n",
    "                ans.append(bigger.pop(0))\n",
    "            # n1 = len(nums1)\n",
    "            # n2 = len(nums2)\n",
    "            # p1 = 0\n",
    "            # p2 = 0\n",
    "            # ans = []\n",
    "            # while p1 <= n1 - 1 and p2 <= n2 - 1:\n",
    "            #     if nums1[p1] > nums2[p2]:\n",
    "            #         ans.append(nums1[p1])\n",
    "            #         p1 += 1\n",
    "            #     else:\n",
    "            #         ans.append(nums2[p2])\n",
    "            #         p2 += 1\n",
    "            # if p1 <= n1 - 1:\n",
    "            #     while p1 <= n1 - 1:\n",
    "            #         ans.append(nums1[p1])\n",
    "            #         p1 += 1\n",
    "            # if p2 <= n2 -1:\n",
    "            #     while p2 <= n2 - 1:\n",
    "            #         ans.append(nums2[p2])\n",
    "            #         p2 += 1\n",
    "            return ans\n",
    "        \n",
    "        res = []\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        for i in range(k + 1):\n",
    "            k1 = i\n",
    "            k2 = k - i\n",
    "            if k1 <= n and k2 <= m:\n",
    "                res.append(merge(find(nums1, k1), find(nums2, k2)))\n",
    "                print(find(nums1, k1))\n",
    "                print(find(nums2, k2))\n",
    "                print(merge(find(nums1, k1), find(nums2, k2)))\n",
    "                print(\"---\")\n",
    "        \n",
    "        return max(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        rst = []\n",
    "        for i in range(k+1):\n",
    "            if i <= len(nums1) and k - i <= len(nums2):\n",
    "                rst.append(self.merge(self.pick_max(nums1, i), self.pick_max(nums2, k - i)))\n",
    "        return max(rst)\n",
    "\n",
    "    def merge(self, l1, l2):\n",
    "        lst = []\n",
    "        while l1 or l2:\n",
    "            bigger = l1 if l1 > l2 else l2\n",
    "            lst.append(bigger.pop(0))\n",
    "        return lst\n",
    "    \n",
    "    def pick_max(self, nums, k):\n",
    "        drop = len(nums) - k\n",
    "        st = []\n",
    "        for num in nums:\n",
    "            while st and drop and st[-1] < num:\n",
    "                st.pop()\n",
    "                drop -= 1\n",
    "            st.append(num)\n",
    "        return st[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def pick_max(nums, k):\n",
    "            \"\"\"\n",
    "            从 nums 中挑选 k 个数字组成的最大数\n",
    "            \"\"\"\n",
    "            stack = []\n",
    "            drop = len(nums) - k\n",
    "            for num in nums:\n",
    "                while drop and stack and stack[-1] < num:\n",
    "                    stack.pop()\n",
    "                    drop -= 1\n",
    "                stack.append(num)\n",
    "            return stack[:k]\n",
    "\n",
    "        def merge(A, B):\n",
    "            \"\"\"\n",
    "            将 A 和 B 组合时候能够组成的最大数\n",
    "            \"\"\"\n",
    "            ans = []\n",
    "            while A or B:\n",
    "                bigger = A if A > B else B\n",
    "                ans.append(bigger[0])\n",
    "                bigger.pop(0)\n",
    "            return ans\n",
    "\n",
    "        merge_s = []\n",
    "        for i in range(k + 1):\n",
    "            if i <= len(nums1) and k - i <= len(nums2):\n",
    "                merge_s.append(merge(pick_max(nums1, i), pick_max(nums2, k-i)))\n",
    "\n",
    "        return max(merge_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        def pick_max(nums, k):\n",
    "            if k == 0:\n",
    "                return []\n",
    "            n = len(nums)\n",
    "            if k == n:\n",
    "                return nums.copy()\n",
    "            else:\n",
    "                drop = n - k\n",
    "                stack = []\n",
    "                for d in nums:\n",
    "                    while stack and drop > 0 and stack[-1] < d:\n",
    "                        drop -= 1\n",
    "                        stack.pop()\n",
    "                    stack.append(d)\n",
    "                return stack[:k]\n",
    "\n",
    "        def merge(nums1, nums2):\n",
    "            ans = []\n",
    "            while nums1 or nums2:\n",
    "                bigger = nums1 if nums1 > nums2 else nums2\n",
    "                ans.append(bigger.pop(0))\n",
    "            return ans\n",
    "\n",
    "        return max([merge(pick_max(nums1, i), pick_max(nums2, k - i)) for i in range(k + 1) if\n",
    "                    i <= len(nums1) and k - i <= len(nums2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "        def pick_max(nums, k):\n",
    "            stack = []\n",
    "            l = len(nums) - k\n",
    "            for num in nums:\n",
    "                while stack and num > stack[-1] and l > 0:\n",
    "                    stack.pop()\n",
    "                    l -= 1\n",
    "                stack.append(num)\n",
    "            return stack[0:k]\n",
    "\n",
    "        def plus_num(nums1, nums2):\n",
    "            stack = []\n",
    "            while nums1 or nums2:\n",
    "                if nums1 >= nums2:\n",
    "                    stack.append(nums1[0])\n",
    "                    nums1.pop(0)\n",
    "                else:\n",
    "                    stack.append(nums2[0])\n",
    "                    nums2.pop(0)\n",
    "            return stack\n",
    "\n",
    "        ans = []\n",
    "        for i in range(k + 1):\n",
    "            if len(nums1) >= i and len(nums2) >= k - i:\n",
    "                ans.append(plus_num(pick_max(nums1, i), pick_max(nums2, k - i)))\n",
    "        print(ans)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self,nums1,nums2,k):\n",
    "        m=len(nums1)\n",
    "        n=len(nums2)\n",
    "        maxtuple=(0,)\n",
    "        # if k<=min(m,n):\n",
    "        #     if n < m:\n",
    "        #         nums1 = nums2\n",
    "        #         maxtuple = findmaxtuple(nums1, k)\n",
    "        # else:\n",
    "        for i in range(k+1):\n",
    "            if i>m or k-i>n:\n",
    "                continue\n",
    "            tmp=func2(findmaxtuple(nums1, i),findmaxtuple(nums2, k-i))\n",
    "            maxtuple=max(tmp,maxtuple)\n",
    "        return maxtuple\n",
    "def findmaxtuple(nums, k):#取最大\n",
    "\n",
    "    if k==0:\n",
    "        return ()\n",
    "    n = len(nums)\n",
    "    if k==n:\n",
    "        return tuple(nums)\n",
    "    idx=maxindex(nums[:n-k+1])\n",
    "    return (nums[idx],)+findmaxtuple(nums[idx+1:], k-1)\n",
    "def maxindex(nums):\n",
    "    idx=0\n",
    "    for i in range(len(nums)):\n",
    "        if nums[idx]<nums[i]:\n",
    "            idx=i\n",
    "    return idx\n",
    "def func2(tuple1,tuple2):\n",
    "    if not tuple2:\n",
    "        return tuple1\n",
    "    if not tuple1:\n",
    "        return tuple2\n",
    "    if tuple1>tuple2:\n",
    "        tuple2,tuple1=tuple1,tuple2\n",
    "    return (tuple2[0],)+func2(tuple1,tuple2[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge_nums(self, nums1: List[int], nums2: List[int]):\n",
    "        i = 0\n",
    "        j = 0        \n",
    "        result = []\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            num1 = nums1[i]\n",
    "            num2 = nums2[j]\n",
    "            if num1 > num2:\n",
    "                result.append(num1)\n",
    "                i += 1\n",
    "            elif num2 > num1:\n",
    "                result.append(num2)\n",
    "                j += 1\n",
    "            elif len(nums1) - 1 == i and len(nums2) - 1 == j:\n",
    "                result.append(num1)\n",
    "                i += 1\n",
    "            else:\n",
    "                len_res = max(len(nums1) - i, len(nums2) - j)\n",
    "\n",
    "                for k in range(1, len_res + 1):\n",
    "                    next1 = nums1[i+k] if i +k < len(nums1) else nums1[i]\n",
    "                    next2 = nums2[j+k] if j +k < len(nums2) else nums2[j]\n",
    "                    if next1 > next2:\n",
    "                        result.append(num1)\n",
    "                        i += 1\n",
    "                        break\n",
    "                    elif next1 < next2:\n",
    "                        result.append(num2)\n",
    "                        j += 1\n",
    "                        break\n",
    "                else:\n",
    "                    result.append(num1)\n",
    "                    i += 1\n",
    "        if i < len(nums1):\n",
    "            result += nums1[i:]\n",
    "        if j < len(nums2):\n",
    "            result += nums2[j:]\n",
    "        return result\n",
    "\n",
    "    def _maxNumber(self, nums: List[int], k: int) -> List[int]:\n",
    "        result = []\n",
    "        if k == 0:\n",
    "            return result\n",
    "        for i, num in enumerate(nums):\n",
    "            while result and result[-1] < num and len(result) + len(nums) - i > k:\n",
    "                result.pop()\n",
    "            if len(result) < k:\n",
    "                result.append(num)\n",
    "        return result\n",
    "\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        if len(nums1) + len(nums2) > k:\n",
    "            nums_list = []\n",
    "            temp = []\n",
    "            for i in range(min((len(nums1) + 1, len(nums2) + 1, k+1))):\n",
    "                if len(nums1) <= len(nums2):\n",
    "                    maxNum1 = self._maxNumber(nums1, i)\n",
    "                    maxNum2 = self._maxNumber(nums2, k-i)\n",
    "                else:\n",
    "                    maxNum1 = self._maxNumber(nums2, i)\n",
    "                    maxNum2 = self._maxNumber(nums1, k-i) \n",
    "                nums_list.append(self.merge_nums(maxNum1, maxNum2))\n",
    "                temp.append((maxNum1, maxNum2))\n",
    "            return max(nums_list)\n",
    "        else:\n",
    "            return self.merge_nums(nums1, nums2)\n",
    "        return self.merge_nums([5, 5], [4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def maxIndex(nums):\n",
    "    return nums.index(max(nums))\n",
    "def getMaxTuple(nums,i):\n",
    "    if i == 0:\n",
    "        return ()\n",
    "    n = len(nums)\n",
    "    idx = maxIndex(nums[:n-i+1])\n",
    "    return (nums[idx],) + getMaxTuple(nums[idx+1:],i-1)\n",
    "\n",
    "def joinMaxTuple(tuple1,tuple2):\n",
    "    if not tuple2:\n",
    "        return tuple1\n",
    "    if not tuple1:\n",
    "        return tuple2\n",
    "    if tuple1>tuple2:\n",
    "        tuple2, tuple1 = tuple1,tuple2\n",
    "    return (tuple2[0],) + joinMaxTuple(tuple1,tuple2[1:])\n",
    "\n",
    "def maxNumbe(nums1,nums2,k):\n",
    "    n1 = len(nums1)\n",
    "    n2 = len(nums2)\n",
    "    res = (0,)\n",
    "    for i in range(k+1):\n",
    "        j = k-i\n",
    "        if i > n1 or j> n2:\n",
    "            continue\n",
    "        if i <= n1 and j <= n2:\n",
    "            tuple1 = getMaxTuple(nums1,i)\n",
    "            tuple2 = getMaxTuple(nums2,j)\n",
    "            if res < joinMaxTuple(tuple1,tuple2):\n",
    "                res = joinMaxTuple(tuple1,tuple2)\n",
    "    return res\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        return maxNumbe(nums1,nums2,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def maxIndex(nums):\n",
    "    return nums.index(max(nums))\n",
    "def getMaxTuple(nums,i):\n",
    "    if i == 0:\n",
    "        return ()\n",
    "    n = len(nums)\n",
    "    idx = maxIndex(nums[:n-i+1])\n",
    "    return (nums[idx],) + getMaxTuple(nums[idx+1:],i-1)\n",
    "\n",
    "def joinMaxTuple(tuple1,tuple2):\n",
    "    if not tuple2:\n",
    "        return tuple1\n",
    "    if not tuple1:\n",
    "        return tuple2\n",
    "    if tuple1>tuple2:\n",
    "        tuple2, tuple1 = tuple1,tuple2\n",
    "    return (tuple2[0],) + joinMaxTuple(tuple1,tuple2[1:])\n",
    "\n",
    "def maxNumbe(nums1,nums2,k):\n",
    "    n1 = len(nums1)\n",
    "    n2 = len(nums2)\n",
    "    res = (0,)\n",
    "    for i in range(k+1):\n",
    "        j = k-i\n",
    "        if i > n1 or j> n2:\n",
    "            continue\n",
    "        if i <= n1 and j <= n2:\n",
    "            tuple1 = getMaxTuple(nums1,i)\n",
    "            tuple2 = getMaxTuple(nums2,j)\n",
    "            if res < joinMaxTuple(tuple1,tuple2):\n",
    "                res = joinMaxTuple(tuple1,tuple2)\n",
    "    return res\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        return maxNumbe(nums1,nums2,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def maxIndex(nums):\n",
    "    return nums.index(max(nums))\n",
    "def getMaxTuple(nums,i):\n",
    "    if i == 0:\n",
    "        return ()\n",
    "    n = len(nums)\n",
    "    idx = maxIndex(nums[:n-i+1])\n",
    "    return (nums[idx],) + getMaxTuple(nums[idx+1:],i-1)\n",
    "\n",
    "def joinMaxTuple(tuple1,tuple2):\n",
    "    if not tuple2:\n",
    "        return tuple1\n",
    "    if not tuple1:\n",
    "        return tuple2\n",
    "    if tuple1>tuple2:\n",
    "        tuple2, tuple1 = tuple1,tuple2\n",
    "    return (tuple2[0],) + joinMaxTuple(tuple1,tuple2[1:])\n",
    "\n",
    "def maxNumbe(nums1,nums2,k):\n",
    "    n1 = len(nums1)\n",
    "    n2 = len(nums2)\n",
    "    res = (0,)\n",
    "    for i in range(k+1):\n",
    "        j = k-i\n",
    "        if i > n1 or j> n2:\n",
    "            continue\n",
    "        if i <= n1 and j <= n2:\n",
    "            tuple1 = getMaxTuple(nums1,i)\n",
    "            tuple2 = getMaxTuple(nums2,j)\n",
    "            if res < joinMaxTuple(tuple1,tuple2):\n",
    "                res = joinMaxTuple(tuple1,tuple2)\n",
    "    return res\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        return maxNumbe(nums1,nums2,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self,nums1, nums2, k):\n",
    "        def findmax(nums,n):\n",
    "\n",
    "            tuples=()\n",
    "            count=-1\n",
    "            last=-1\n",
    "            for i in range(n):\n",
    "                count+=1\n",
    "                tempnum=nums[last+1:len(nums)-n+count+1]\n",
    "                curmax=max(tempnum)\n",
    "                #print(\"ssss\",tempnum)\n",
    "                idx=tempnum.index(curmax)\n",
    "                last+=idx+1\n",
    "                tuples+=(curmax,)\n",
    "\n",
    "            #print(tuples)\n",
    "            return tuples\n",
    "\n",
    "        def func2(tuple1,tuple2):\n",
    "            if not tuple1 and not tuple2:\n",
    "                return ()\n",
    "            if not tuple1:\n",
    "                return tuple2\n",
    "            if not tuple2:\n",
    "                return tuple1\n",
    "            if tuple1>tuple2:\n",
    "                tuple1,tuple2=tuple2,tuple1\n",
    "            return (tuple2[0],)+func2(tuple1,tuple2[1:])\n",
    "            \n",
    "            \n",
    "        \n",
    "        n=len(nums1)\n",
    "        m=len(nums2)\n",
    "        tup=(0,)*k\n",
    "        for i in range(k+1):\n",
    "            if i<=n and k-i<=m:\n",
    "\n",
    "                num1=findmax(nums1,i)+()\n",
    "                num2=findmax(nums2,k-i)+()\n",
    "                print(i,num1)\n",
    "                print(i,num2)\n",
    "                temp = num1+num2\n",
    "                tem=func2(num1,num2)\n",
    "\n",
    "                print(\"dddd\",tem)\n",
    "                tup=max(tup,tem)\n",
    "                print(tup)\n",
    "            continue\n",
    "        # for i in range(k + 1):\n",
    "        #     if k-i <= m and i <= n:\n",
    "        #         num1 = findmax(nums1, k-i)\n",
    "        #         num2 = findmax(nums2, i)\n",
    "        #         temp=func2(num1,num2)\n",
    "        #         print(temp)\n",
    "        #         #tup = max(tup, temp)\n",
    "        #     continue\n",
    "        return tup  \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merger(self, list1, list2):\n",
    "        # print(list1, list2)\n",
    "        n1 = len(list1)\n",
    "        n2 = len(list2)\n",
    "        if not list1:\n",
    "            return list2\n",
    "        if not list2:\n",
    "            return list1\n",
    "        res = []\n",
    "        i = j = 0\n",
    "        s1 = ''.join([str(list1[i]) for i in range(n1)])\n",
    "        s2 = ''.join([str(list2[i]) for i in range(n2)])\n",
    "        while i < n1 and j < n2:\n",
    "            if s1[i:] > s2[j:]:\n",
    "                res.append(list1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                res.append(list2[j])\n",
    "                j += 1\n",
    "        if i < n1:\n",
    "            return res + list1[i:]\n",
    "        if j < n2:\n",
    "            return res + list2[j:]\n",
    "        return res\n",
    "\n",
    "    def getmax(self, nums, nleft):\n",
    "        if nleft > len(nums):\n",
    "            return []\n",
    "        if nleft == len(nums):\n",
    "            return nums\n",
    "        k = len(nums) - nleft\n",
    "        chkstack = list()\n",
    "        for i, val in enumerate(nums):\n",
    "            while k > 0 and chkstack and chkstack[-1] < val:\n",
    "                chkstack.pop()\n",
    "                k -= 1\n",
    "            chkstack.append(val)\n",
    "        for _ in range(k):\n",
    "            chkstack.pop()\n",
    "        return chkstack\n",
    "\n",
    "\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        res1 = [[]]\n",
    "        res2 = [[]]\n",
    "        ans = []\n",
    "        for ki in range(1, k+1):\n",
    "            res1.append(self.getmax(nums1, ki))\n",
    "            res2.append(self.getmax(nums2, ki))\n",
    "        for i in range(k+1):\n",
    "            x = self.merger(res1[i], res2[k-i])\n",
    "            if len(x) == k:\n",
    "                ans.append(x)\n",
    "        # print(res1)\n",
    "        # print(res2)\n",
    "        # print(ans)\n",
    "        maxval = ''\n",
    "        maxloc = -1\n",
    "        for i, v in enumerate(ans):\n",
    "            curv = [str(x) for x in v]\n",
    "            curs = ''.join(curv)\n",
    "            if maxval < curs:\n",
    "                maxval = curs\n",
    "                maxloc = i\n",
    "        return ans[maxloc]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        tmp1 = self.help(nums1, k)\n",
    "        tmp2 = self.help(nums2, k)\n",
    "        # print(m, n)\n",
    "        res, res_val = [], \"0\"\n",
    "        for i in range(k + 1):\n",
    "            if len(tmp1[i]) + len(tmp2[k - i]) == k:\n",
    "                cur = self.calculate(tmp1[i], tmp2[k - i])\n",
    "                if \"\".join(str(s) for s in cur) > \"\".join(str(s) for s in res):\n",
    "                    res = cur\n",
    "            else:\n",
    "                pass\n",
    "                # print(len(tmp1[i]) + len(tmp2[k - i]))\n",
    "        return res\n",
    "\n",
    "    def calculate(self, nums1, nums2):\n",
    "        res = []\n",
    "        idx1, idx2 = 0, 0\n",
    "        while idx1 < len(nums1) or idx2 < len(nums2):\n",
    "            v1 = nums1[idx1] if idx1 < len(nums1) else float('-inf')\n",
    "            v2 = nums2[idx2] if idx2 < len(nums2) else float('-inf')      \n",
    "            if v1 > v2:\n",
    "                res.append(v1)\n",
    "                idx1 += 1\n",
    "            elif v1 < v2:\n",
    "                res.append(v2)\n",
    "                idx2 += 1\n",
    "            else:\n",
    "                delta = 1\n",
    "                while idx1 + delta < len(nums1) or idx2 + delta < len(nums2):\n",
    "                    v1_next = nums1[idx1 + delta] if idx1 + delta < len(nums1) else float('-inf')\n",
    "                    v2_next = nums2[idx2 + delta] if idx2 + delta < len(nums2) else float('-inf')         \n",
    "                    if v1_next != v2_next:\n",
    "                        break\n",
    "                    delta += 1\n",
    "                if v1_next > v2_next:\n",
    "                    res.append(v1)\n",
    "                    idx1 += 1\n",
    "                else:\n",
    "                    res.append(v2)\n",
    "                    idx2 += 1                                \n",
    "        # print(res)\n",
    "        return res\n",
    "\n",
    "    def help(self, nums, k):\n",
    "        m = len(nums)\n",
    "        res = [[]]\n",
    "        for i in range(1, k + 1):\n",
    "            remove, ss = 0, []\n",
    "            for idx in range(m):\n",
    "                while ss and ss[-1] < nums[idx] and remove < m - i:\n",
    "                    ss.pop()\n",
    "                    remove += 1\n",
    "                if len(ss) < i:\n",
    "                    ss.append(nums[idx])\n",
    "                else:\n",
    "                    remove += 1\n",
    "            res.append(ss)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 从一个数组中取全部的 k个元素\n",
    "    def pick(self, nums, k):\n",
    "        n = len(nums)\n",
    "        if k == 0:\n",
    "            return []\n",
    "        if n == k:\n",
    "            return nums\n",
    "\n",
    "        count, stack = 0, []\n",
    "        for i in range(n):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(nums[i])\n",
    "            else:\n",
    "                while len(stack) > 0 and int(nums[i]) > int(stack[-1]):\n",
    "                    stack.pop()\n",
    "                    count = count + 1\n",
    "                    if count == n-k:\n",
    "                        return stack + nums[i:]\n",
    "                if len(stack) < k:\n",
    "                    stack.append(nums[i])\n",
    "                else:\n",
    "                    count = count + 1\n",
    "        return stack\n",
    "\n",
    "    # 将从第一个数组和第二个数组中取出来的数拼起来\n",
    "    def merge(self, res1, res2):\n",
    "        if len(res1) == 0:\n",
    "            return res2\n",
    "        if len(res2) == 0:\n",
    "            return res1\n",
    "        if res1 == res2:\n",
    "            if len(res1) == 1:\n",
    "                return res1 + res2\n",
    "            else:\n",
    "                i = 0\n",
    "                while True:\n",
    "                    if i >= len(res1)-1:\n",
    "                        return res1 + res2\n",
    "                    if res1[i] > res1[i+1]:\n",
    "                        return res1[:i+1] + res2[:i+1] + self.merge(res1[i+1:], res2[i+1:])\n",
    "                    elif res1[i] < res1[i+1]:\n",
    "                        return res1[:i+1] + self.merge(res1[i+1:], res2[:])\n",
    "                    i = i + 1\n",
    "\n",
    "        if res1[0] > res2[0]:\n",
    "            return [res1[0]] + self.merge(res1[1:], res2[:])\n",
    "        elif res1[0] < res2[0]:\n",
    "            return [res2[0]] + self.merge(res1[:], res2[1:])\n",
    "        else:\n",
    "            # 如果出现了 res1[0]==res2[0]，则考虑 res1[1]和 res2[1]\n",
    "            i = 1\n",
    "            while True:\n",
    "                # 如果 res1和 res2有一个短一点，取不到下一位数\n",
    "                # 则哪边长就从哪边取下一个数\n",
    "                if len(res1) > i and len(res2) == i:\n",
    "                    return [res1[0]] + self.merge(res1[1:], res2[:])\n",
    "                elif len(res1) == i and len(res2) > i:\n",
    "                    return [res2[0]] + self.merge(res1[:], res2[1:])\n",
    "                # 如果 res1[1]和 res2[1]不相等，则哪边大就从哪边取下一个数\n",
    "                # 否则进一步考虑 res1[2]和 res2[2]\n",
    "                elif res1[i] > res2[i]:\n",
    "                    return [res1[0]] + self.merge(res1[1:], res2[:])\n",
    "                elif res1[i] < res2[i]:\n",
    "                    return [res2[0]] + self.merge(res1[:], res2[1:])\n",
    "                i = i + 1\n",
    "\n",
    "    # 比较两个 k位答案的大小\n",
    "    def judge(self, r1, r2):\n",
    "        k = len(r1)\n",
    "        for i in range(k):\n",
    "            if r1[i] > r2[i]:\n",
    "                return True\n",
    "            elif r1[i] < r2[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def maxNumber(self, nums1, nums2, k):\n",
    "        l1, l2 = len(nums1), len(nums2)\n",
    "        result = []\n",
    "        for i in range(l1+1):\n",
    "            if l2 >= k-i:\n",
    "                res1, res2 = self.pick(nums1, i), self.pick(nums2, k-i)\n",
    "                result.append(self.merge(res1, res2))\n",
    "        while len(result) >= 2:\n",
    "            if self.judge(result[0], result[1]):\n",
    "                result.pop(1)\n",
    "            else:\n",
    "                result.pop(0)\n",
    "        return result[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def maxIndex(nums):\n",
    "    return nums.index(max(nums))\n",
    "def func1(nums,i):\n",
    "    if i == 0:\n",
    "        return ()\n",
    "    n = len(nums)\n",
    "    idx = maxIndex(nums[:n - i + 1])\n",
    "    return (nums[idx],) + func1(nums[idx + 1:], i - 1)\n",
    "def maxtuple(a1,b1):\n",
    "    if not a1:\n",
    "        return b1\n",
    "    if not b1:\n",
    "        return a1\n",
    "    if a1 > b1:\n",
    "        b1,a1 = a1,b1\n",
    "    return (b1[0],)+maxtuple(a1,b1[1:])\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        res = []\n",
    "        ans = []\n",
    "        for i in range(k+1):\n",
    "            if i > m or k-i > n:\n",
    "                continue\n",
    "            a1 = func1(nums1,i)\n",
    "            b1 = func1(nums2,k-i)\n",
    "            c = maxtuple(a1,b1)\n",
    "            res.append(c)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def get_sequence(nums: tuple, cnt: int)->tuple:\n",
    "            if cnt == len(nums):\n",
    "                return nums\n",
    "            buf = get_sequence(nums, cnt + 1)\n",
    "            for i in range(len(buf) - 1):\n",
    "                if buf[i] < buf[i+1]:\n",
    "                    return buf[:i] + buf[i+1:]\n",
    "            return buf[:-1]\n",
    "\n",
    "        def combine(arr1: tuple, arr2: tuple) -> list:\n",
    "            i = j = 0\n",
    "            result = []\n",
    "            while i < len(arr1) and j < len(arr2):\n",
    "                if arr1[i:] >= arr2[j:]:# or (arr1[i] == arr2[j] and arr1[i:] > arr2[j:]):\n",
    "                    result.append(arr1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    result.append(arr2[j])\n",
    "                    j += 1\n",
    "            return result + list(arr1[i:] + arr2[j:])\n",
    "        \n",
    "        result = [0] * k\n",
    "        nums1 = tuple(nums1)\n",
    "        nums2 = tuple(nums2)\n",
    "        return max([combine(get_sequence(nums1, i), get_sequence(nums2, k - i)) for i in range(max(k - len(nums2), 0), min(len(nums1), k) + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def get_sequence(nums: tuple, cnt: int)->tuple:\n",
    "            if cnt == len(nums):\n",
    "                return nums\n",
    "            buf = get_sequence(nums, cnt + 1)\n",
    "            for i in range(len(buf) - 1):\n",
    "                if buf[i] < buf[i+1]:\n",
    "                    return buf[:i] + buf[i+1:]\n",
    "            return buf[:-1]\n",
    "\n",
    "        def combine(arr1: tuple, arr2: tuple) -> list:\n",
    "            i = j = 0\n",
    "            result = []\n",
    "            while i < len(arr1) and j < len(arr2):\n",
    "                if arr1[i:] >= arr2[j:]:\n",
    "                    result.append(arr1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    result.append(arr2[j])\n",
    "                    j += 1\n",
    "            return result + list(arr1[i:] + arr2[j:])\n",
    "        \n",
    "        result = [0] * k\n",
    "        nums1 = tuple(nums1)\n",
    "        nums2 = tuple(nums2)\n",
    "        return max([combine(get_sequence(nums1, i), get_sequence(nums2, k - i)) for i in range(max(k - len(nums2), 0), min(len(nums1), k) + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def find_biggest_sublist(nums, k):\n",
    "            del_num = len(nums)-k\n",
    "            stack = []\n",
    "            for i in nums: \n",
    "                while stack and (del_num>0) and i>stack[-1]:\n",
    "                    stack.pop()\n",
    "                    del_num -= 1\n",
    "                stack.append(i)\n",
    "            return(stack[:k])\n",
    "\n",
    "        def merge_2_sublist(sub1,sub2):\n",
    "            sub = []\n",
    "            while sub1 or sub2:\n",
    "                if sub1 and sub1 > sub2:\n",
    "                    sub.append(sub1.pop(0))\n",
    "                else:\n",
    "                    sub.append(sub2.pop(0))\n",
    "            return(sub)\n",
    "        \n",
    "        res = []\n",
    "        for k1 in range(k+1):\n",
    "            k2 = k-k1\n",
    "            if (k1<=len(nums1)) and (k2<=len(nums2)):\n",
    "                sub1 = find_biggest_sublist(nums1,k1)\n",
    "                sub2 = find_biggest_sublist(nums2,k2)\n",
    "                sub = merge_2_sublist(sub1,sub2)\n",
    "                res.append(sub)\n",
    "        print(res)\n",
    "        return(max(res))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
